import java.io.*;
import java.util.*;
import java.util.Map.Entry;

public class E {
	FastScanner in;
	PrintWriter out;
	boolean systemIO = true;

	public class DSU {
		int[] sz;
		int[] p;

		public DSU(int n) {
			sz = new int[n];
			p = new int[n];
			for (int i = 0; i < p.length; i++) {
				p[i] = i;
				sz[i] = 1;
			}
		}

		public int get(int x) {
			if (x == p[x]) {
				return x;
			}
			int par = get(p[x]);
			p[x] = par;
			return par;
		}

		public boolean unite(int a, int b) {
			int pa = get(a);
			int pb = get(b);
			if (pa == pb) {
				return false;
			}
			if (sz[pa] < sz[pb]) {
				p[pa] = pb;
				sz[pb] += sz[pa];
			} else {
				p[pb] = pa;
				sz[pa] += sz[pb];
			}
			return true;
		}
	}

	public class SegmentTreeAdd {
		int pow;
		long[] min;
		long[] delta;
		boolean[] flag;

		public SegmentTreeAdd(long[] a) {
			pow = 1;
			while (pow < a.length) {
				pow *= 2;
			}
			flag = new boolean[2 * pow];
			min = new long[2 * pow];
			delta = new long[2 * pow];
			for (int i = 0; i < min.length; i++) {
				min[i] = Long.MAX_VALUE / 2;
			}
			for (int i = 0; i < a.length; i++) {
				min[pow + i] = a[i];
			}
			for (int i = pow - 1; i > 0; i--) {
				min[i] = f(min[2 * i], min[2 * i + 1]);
			}
		}

		public long get(int l, int r) {
			return get(1, 0, pow, l, r);
		}

		private long get(int v, int tl, int tr, int l, int r) {
			push(v, tl, tr);
			if (l >= tr || r <= tl) {
				return Long.MAX_VALUE / 2;
			}
			if (l <= tl && r >= tr) {
				return min[v];
			}
			int tm = (tl + tr) / 2;
			return f(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm, tr, l, r));
		}

		public void set(int l, int r, long x) {
			set(1, 0, pow, l, r, x);
		}

		private void set(int v, int tl, int tr, int l, int r, long x) {
			push(v, tl, tr);
			if (l >= tr || r <= tl) {
				return;
			}
			if (l <= tl && r >= tr) {
				delta[v] += x;
				flag[v] = true;
				push(v, tl, tr);
				return;
			}
			int tm = (tl + tr) / 2;
			set(2 * v, tl, tm, l, r, x);
			set(2 * v + 1, tm, tr, l, r, x);
			min[v] = f(min[2 * v], min[2... What is the time complexity of the previous code?