import java.util.*;
import java.util.stream.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;

class Common {
	static NoSuchElementException dequeEmpty() {
		return new NoSuchElementException("The deque is empty");
	}
}

class AryDeque<T> {
	private Object[] data = new Object[2];
	private int lo = 0;
	private int hi = 0;
	private boolean grow32;

	public AryDeque(boolean grow32) {
		this.grow32 = grow32;
	}

	public void addFront(T value) {
		grow(1);
		lo = dec(lo);
		data[lo] = value;
	}

	public void addBack(T value) {
		grow(1);
		data[hi] = value;
		hi = inc(hi);
	}

	public T popFront() {
		if (lo == hi) throw Common.dequeEmpty();
		T value = (T) data[lo];
		data[lo] = null;
		lo = inc(lo);
		shrink();
		return value;
	}

	public T popBack() {
		if (lo == hi) throw Common.dequeEmpty();
		hi = dec(hi);
		T value = (T) data[hi];
		data[hi] = null;
		shrink();
		return value;
	}

	private int dec(int i) {
		return --i >= 0 ? i : i + data.length;
	}

	private int inc(int i) {
		return ++i < data.length ? i : i - data.length;
	}

	private int getItemsCount() {
		return lo == hi ? 0 : lo < hi ? hi - lo : data.length - lo + hi;
	}

	private void grow(int by) {
		int itemsCount = getItemsCount();
		if (itemsCount + by + 1 > data.length) {
			reallocate(max(itemsCount + by + 1, grow32 ? data.length + max(4, data.length / 2) : 2 * data.length));
		}
	}

	private void shrink() {
		int itemsCount = getItemsCount();
		if ((itemsCount == 0 || data.length > 8) && itemsCount <= data.length / 4) {
			reallocate(itemsCount == 0 ? 2 : grow32 ? itemsCount + max(4, itemsCount) : 2 * itemsCount);
		}
	}

	private void reallocate(int newSize) {
		assert newSize >= 1 + getItemsCount();

		Object[] newData = new Object[newSize];
		if (lo != hi) {
			System.arraycopy(data, lo, newData, 0, (lo < hi ? hi : data.length) - lo);
			if (lo > hi) System.arraycopy(data, 0, newData, data.length - lo, hi);
		}
		hi = getItemsCount();
		lo = 0;
		data = newData;
	}

	public String dump() {
		return String.format("%s lo = %d hi = %d", Arrays.toString(data), lo, hi);
	}

	public List<T> toList() {
		List<T> result = new ArrayList<T>();
		if (lo != hi) {
			result.addAll(Arrays.asList((T[]) data).subList(lo, lo < hi ? hi : data.length));
			if (lo > hi) result.addAll(Arrays.asList((T[]) data).subList(0, hi));
		}
		return result;
	}
}

/**
 * Deque built over linked list.
 */
class LLDeque<T> {
	static class Node<T> {
		T value;
		Node prev, next;
	}

	Node<T> first, last;

	public void addFront(T value) {
		Node<T> n = new Node<T>();
		n.value = value;
		n.next = first;
		if (first == null) last = n; else first.prev = n;
		first = n;
	}

	public void addBack(T value) {
		Node<T> n = new Node<T>();
		n.value = value;
		n.prev = last;
		if (last == null) first = n; else last.next = n;
		last = n;
	}

	public T popFront() {
		if (first == null) throw Common.dequeEmpty();
		T value = first.value;
		first = first.next;
		if (first == null) last = null; else first.prev = null;
		return value;
	}

	public T popBack() {
		if (last == null) throw Common.dequeEmpty();
		T value = last.value;
		last = last.prev;
		if (last == null) first = null; else last.next = null;
		return value;
	}

	public List<T> toList() {
		List<T> result = new ArrayList<T>();
		for (Node<T> n = first; n != null; n = n.next) {
			result.add(n.value);
		}
		return result;
	}
}

/**
 * Deque built over unrolled circular linked list with at most 2 "cached" empty nodes
 * right after tail and before head.
 * Thanks to these empty nodes, pushes and pops that happen to repeatedly over-
 * and underflow head and tail won't provoke excessive amount of allocations.
 *
 * So the possible configurations are:
 * head -> (head)
 * — starting configuration, head == tail == head.next == head.prev.
 *
 * head -> ... ... ... -> tail -> (head)
 * — no empty node after tail, tail.next == head,
 * -or-
 * head -> ... ... ... -> tail -> empty_node -> (head)
 * — 1 empty node after tail, tail.next.next == head.
 * Should an edge node become empty, it will be kept for reuse.
 *
 * head -> ... ... ... -> tail -> empty_node0 -> empty_node1 -> (head)
 * — 2 empty nodes between tail and head.
 * If another node becomes empty, one of these 3 finally gets disposed of.
 */
class UCLLDeque<T> {
	static class Node<T> {
		Object[] values;
		Node prev, next;

		Node(int size) {
			values = new Object[size];
		}
	}
	Node<T> headNode, tailNode;
	int iHead, iTail;

	public UCLLDeque() {
		headNode = new Node<T>(4);
		tailNode = headNode;
		headNode.prev = tailNode;
		headNode.next = tailNode;
	}

	public void addFront(T value) {
		if (iHead == 0) {
			headNode = headNode.prev != tailNode ? headNode.prev : insertNode(createNode(), true, headNode);
			iHead = headNode.values.length;
		}
		headNode.values[--iHead] = value;
	}

	public void addBack(T value) {
		tailNode.values[iTail++] = value;
		if (iTail == tailNode.values.length) {
			tailNode = tailNode.next != headNode ? tailNode.next : insertNode(createNode(), false, tailNode);
			iTail = 0;
		}
	}

	public T popFront() {
		if (headNode == tailNode && iHead == iTail) {
			throw Common.dequeEmpty();
		}
		T value = (T) headNode.values[iHead];
		headNode.values[iHead++] = null;
		if (iHead == headNode.values.length) {
			if (headNode.prev != tailNode && headNode.prev.prev != tailNode) {
				removeNode(headNode.prev.prev);
			}
			headNode = headNode.next;
			iHead = 0;
		}
		return value;
	}

	public T popBack() {
		if (tailNode == headNode && iTail == iHead) {
			throw Common.dequeEmpty();
		}
		if (iTail == 0) {
			if (tailNode.next != headNode && tailNode.next.next != headNode) {
				removeNode(tailNode.next.next);
			}
			tailNode = tailNode.prev;
			iTail = tailNode.values.length;
		}
		T value = (T) tailNode.values[--iTail];
		tailNode.values[iTail] = null;
		return value;
	}

	private int calcItemsCount() {
		int count = 0;
		for (Node<T> n = headNode, prevN = null; prevN != tailNode; prevN = n, n = n.next) {
			count += (n == tailNode ? iTail : n.values.length) - (n == headNode ? iHead : 0);
		}
		return count;
	}

	private Node<T> createNode() {
		return new Node<T>(max(4, calcItemsCount() / 2));
	}

	private Node<T> insertNode(Node node, boolean before, Node adjacent) {
		Node<T> prev = before ? adjacent.prev : adjacent;
		Node<T> next = before ? adjacent : adjacent.next;
		node.prev = prev;
		node.next = next;
		prev.next = node;
		next.prev = node;
		return node;
	}

	private static <T> void removeNode(Node<T> node) {
		Node<T> n_prev = node.prev, n_next = node.next;
		n_prev.next = n_next;
		n_next.prev = n_prev;
	}

	public String dump() {
		StringBuilder r = new StringBuilder(), desc = new StringBuilder();
		r.append("items=").append(calcItemsCount());
		boolean tailSeen = false;
		for (Node<T> n = headNode, stopN = null; n != stopN; stopN = headNode, n = n.next) {
			r.append("\n").append(Arrays.toString(n.values));
			desc.setLength(0);
			if (n == headNode) desc.append(desc.length() > 0 ? ", " : ": ").append("iHead=").append(iHead);
			if (n == tailNode) desc.append(desc.length() > 0 ? ", " : ": ").append("iTail=").append(iTail);
			if (tailSeen) desc.append(desc.length() > 0 ? ", " : ": ").append("dangling");
			r.append(desc);
			tailSeen |= n == tailNode;
		}
		return r.toString();
	}

	public List<T> toList() {
		List<T> result = new ArrayList<T>();
		for (Node<T> n = headNode, prevN = null; prevN != tailNode; prevN = n, n = n.next) {
			result.addAll(((List<T>) Arrays.asList(n.values)).subList(
				n == headNode ? iHead : 0, n == tailNode ? iTail : n.values.length));
		}
		return result;
	}
}

class UCLLDequeTracer<T> {
	private UCLLDeque<T> deque;
	private PrintStream out;

	public UCLLDequeTracer(UCLLDeque<T> deque, PrintStream out) {
		this.deque = deque;
		this.out = out;
	}

	public void addFront(T value) {
		deque.addFront(value);
		out.printf("addFront(%s): %s\n\n", value, deque.dump());
	}

	public void addBack(T value) {
		deque.addBack(value);
		out.printf("addBack(%s): %s\n\n", value, deque.dump());
	}

	public T popFront() {
		T value = deque.popFront();
		out.printf("popFront() -> %s: %s\n\n", value, deque.dump());
		return value;
	}

	public T popBack() {
		T value = deque.popBack();
		out.printf("popBack() -> %s: %s\n\n", value, deque.dump());
		return value;
	}
}

class Application {
	static final int OP_ADD_FRONT = 0;
	static final int OP_ADD_BACK = 1;
	static final int OP_POP_FRONT = 2;
	static final int OP_POP_BACK = 3;
	static final int DUMMIES = 10;
	static final int LEN_LIMIT = 100000;
	static final int OPS_COUNT = 4000000;

	private static int[] generatePlan() {
		var ops = new ArrayList<Integer>();
		var rand = new Random(1);
		int len = 0, maxlen = 0;
		for (int i = 0; i < OPS_COUNT; i++) {
			if (len == 0 || len < LEN_LIMIT && len < rand.nextInt(1 + rand.nextInt(1 + rand.nextInt(1 + 6 * LEN_LIMIT)))) {
				int n = min(1 + rand.nextInt(1 + rand.nextInt(1 + rand.nextInt(1 + rand.nextInt(600)))), LEN_LIMIT - len);
				ops.add(rand.nextInt(2) == 0 ? OP_ADD_FRONT : OP_ADD_BACK);
				ops.add(n);
				ops.add(rand.nextInt(DUMMIES));
				len += n;
				maxlen = max(len, maxlen);
			} else {
				int n = min(1 + rand.nextInt(1 + rand.nextInt(1 + rand.nextInt(1 + rand.nextInt(1200)))), len);
				ops.add(rand.nextInt(2) == 0 ? OP_POP_FRONT : OP_POP_BACK);
				ops.add(n);
				len -= n;
			}
		}
		System.out.printf("len after ops=%d, max len during ops=%d\n", len, maxlen);
		return ops.stream().mapToInt(i -> i).toArray();
	}

	static void fusedBenchmarkTest() {
		Integer[] dummies = IntStream.range(0, DUMMIES).map(i -> i*i).boxed().toArray(Integer[]::new);
		var ops = generatePlan();

		final int TRIALS = 3;
		for (int iTrial = 0; iTrial < TRIALS; iTrial++) {
			System.out.printf("%s--- TRIAL %d/%d ---\n", iTrial > 0 ? "\n" : "", 1 + iTrial, TRIALS);

			var q_a2 = new AryDeque<Integer>(false);
			double refTime = benchmark("Deque over array (grow to cap*2, shrink /4 -> /2)",
				() -> {
					for (int iOp = 0; iOp < ops.length; )
						switch (ops[iOp]) {
							case OP_ADD_FRONT: { Integer dummy = dummies[ops[iOp + 2]]; for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a2.addFront(dummy); iOp += 3; break; }
							case OP_ADD_BACK: { Integer dummy = dummies[ops[iOp + 2]]; for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a2.addBack(dummy); iOp += 3; break; }
							case OP_POP_FRONT: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a2.popFront(); iOp += 2; break;
							default: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a2.popBack(); iOp += 2; break;
						}
					return q_a2;
				});

			var q_a32 = new AryDeque<Integer>(true);
			benchmark("Deque over array (grow to cap*3/2, shrink /4 -> /2)",
				() -> {
					for (int iOp = 0; iOp < ops.length; )
						switch (ops[iOp]) {
							case OP_ADD_FRONT: { Integer dummy = dummies[ops[iOp + 2]]; for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a32.addFront(dummy); iOp += 3; break; }
							case OP_ADD_BACK: { Integer dummy = dummies[ops[iOp + 2]]; for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a32.addBack(dummy); iOp += 3; break; }
							case OP_POP_FRONT: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a32.popFront(); iOp += 2; break;
							default: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a32.popBack(); iOp += 2; break;
						}
					return q_a32;
				}, refTime);

			var q_l = new LLDeque<Integer>();
			benchmark("Deque over linked list",
				() -> {
					for (int iOp = 0; iOp < ops.length; )
						switch (ops[iOp]) {
							case OP_ADD_FRONT: { Integer dummy = dummies[ops[iOp + 2]]; for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_l.addFront(dummy); iOp += 3; break; }
							case OP_ADD_BACK: { Integer dummy = dummies[ops[iOp + 2]]; for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_l.addBack(dummy); iOp += 3; break; }
							case OP_POP_FRONT: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_l.popFront(); iOp += 2; break;
							default: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_l.popBack(); iOp += 2; break;
						}
					return q_l;
				}, refTime);

			var q_ul = new UCLLDeque<Integer>();
			benchmark("Deque over unrolled circular linked list",
				() -> {
					for (int iOp = 0; iOp < ops.length; )
						switch (ops[iOp]) {
							case OP_ADD_FRONT: { Integer dummy = dummies[ops[iOp + 2]]; for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_ul.addFront(dummy); iOp += 3; break; }
							case OP_ADD_BACK: { Integer dummy = dummies[ops[iOp + 2]]; for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_ul.addBack(dummy); iOp += 3; break; }
							case OP_POP_FRONT: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_ul.popFront(); iOp += 2; break;
							default: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_ul.popBack(); iOp += 2; break;
						}
					return q_ul;
				}, refTime);

			if (iTrial == 0) {
				var ref = q_a32.toList();
				System.out.printf("\nfinal deque len=%d\n", ref.size());
				var test = q_l.toList();
				checkEqual("Linked list-based deque", test, ref, test.size());
				test = q_ul.toList();
				checkEqual("Unrolled circular linked list-based deque", test, ref, test.size());
			}
		}
	}

	static void checkEqual(String what, Object test, Object ref, Object extra) {
		if (test.equals(ref))
			System.out.printf("%s implementation yielded the same result so is probably correct.\n", what);
		else
			throw new RuntimeException(String.format("%s yielded a different result (%d), one or another is incorrect.", what, extra));
	}

	@FunctionalInterface
	interface BenchmarkPayload {
		abstract Object run();
	}

	static double benchmark(String title, BenchmarkPayload payload) {
		return benchmark(title, payload, -1);
	}

	static double benchmark(String title, BenchmarkPayload payload, double refTime) {
		long start = System.nanoTime();
		Object keepAlive = payload.run();
		double time = (System.nanoTime() - start) * 1e-9;
		System.out.println(String.format(
			"%s: %.2f s%s",
			title, time, refTime >= 0 ? String.format(" (%s)", judgement(time, refTime)) : "", keepAlive));
		return time;
	}

	static String judgement(double time, double refTime) {
		final double absThreshold = 0.3, relThreshold = .1;

		return time <= absThreshold || refTime <= absThreshold ?
			String.format("can't judge, min. required time is %.1f s", absThreshold) :
			Math.max(time, refTime) > (1 + relThreshold) * Math.min(time, refTime) ?
			String.format("%.0f%% %s", Math.abs(time / refTime - 1) * 100, time < refTime ? "faster" : "slower") :
			String.format("no observable difference, min. %.0f%% required", relThreshold * 100);
	}

	public static void main(String[] args) {
		try {
			fusedBenchmarkTest();

			System.out.println();
			/*var q = new UCLLDequeTracer(new UCLLDeque<Integer>(), System.out);
			for (int i = 0; i < 8; i++) {
				q.addFront(i);
			}
			for (int i = 0; i < 8; i++) {
				q.popFront();
			}
			q.addBack(10);
			q.popFront();
			q.addFront(9);*/

			var deque = new UCLLDequeTracer(new UCLLDeque<Integer>(), System.out);
			for (int i = 3; i >= 0; i--) {
				deque.addFront(i);
			}
			for (int i = 4; i <= 7; i++) {
				deque.addBack(i);
			}
			for (int i = 0; i < 4; i++) {
				deque.popFront();
				deque.popBack();
			}
			deque.addBack(1);
			deque.addFront(0);
		} catch (Exception e) {
			StringWriter sw = new StringWriter();
			e.printStackTrace(new PrintWriter(sw));
			System.out.println(sw.toString());
		}
	}
}