public class Main {

	public static void main(String[] args) {
		new Main();
	}

	public Main() {
		FastScanner fs = new FastScanner();
		java.io.PrintWriter out = new java.io.PrintWriter(System.out);
		solve(fs, out);
		out.flush();
	}

	public void solve(FastScanner fs, java.io.PrintWriter out) {
		int N = fs.nextInt(), M = fs.nextInt(), X = fs.nextInt();
		int[][] slime = new int[5][N];
		for (int i = 0;i < N;++ i) {
			int C = fs.nextInt() - 1;
			slime[C][i] = 1;
		}
		int[][] bonus = new int[5][N + 1];
		for (int i = 0;i < M;++ i) {
			int A = fs.nextInt() - 1, B = fs.nextInt() - 1, Y = fs.nextInt();
			bonus[B][N - A] += Y;
		}
		int[][] score = new int[5][];
		for (int i = 0;i < 5;++ i) score[i] = Convolution.convolution998_244_353(slime[i], bonus[i]);
		int ans = X * N;
		for (int i = 0;i < N;++ i) {
			int tmp = X * i;
			for (int j = 0;j < 5;++ j) tmp += score[j][N + i];
			ans = Math.max(ans, tmp);
		}
		out.println(ans);
	}

	final int MOD = 998_244_353;

	int plus(int n, int m) {
		int sum = n + m;
		if (sum >= MOD) sum -= MOD;
		return sum;
	}

	int minus(int n, int m) {
		int sum = n - m;
		if (sum < 0) sum += MOD;
		return sum;
	}

	int times(int n, int m) {
		return (int) ((long) n * m % MOD);
	}

	int divide(int n, int m) {
		return times(n, IntMath.pow(m, MOD - 2, MOD));
	}

	int[] fact, invf;

	void calc(int len) {
		len += 2;
		fact = new int[len];
		invf = new int[len];
		fact[0] = fact[1] = invf[0] = invf[1] = 1;
		for (int i = 2; i < fact.length; ++i) fact[i] = times(fact[i - 1], i);
		invf[len - 1] = divide(1, fact[len - 1]);
		for (int i = len - 1; i > 1; --i) invf[i - 1] = times(i, invf[i]);
	}

	int comb(int n, int m) {
		if (n < m) return 0;
		return times(fact[n], times(invf[n - m], invf[m]));
	}


	public static final class MathLib {

		public static class Barrett {
			private final int mod;
			private final long h, l;
			private final long MAX = 1L << 62;
			private final int MASK = (1 << 31) - 1;

			Barrett(final int mod) {
				this.mod = mod;
				final long t = MAX / mod;
				h = t >>> 31;
				l = t & MASK;
			}

			int reduce(final long x) {
				final long xh = x >>> 31, xl = x & MASK;
				long z = xl * l;
				z = xl * h + xh * l + (z >>> 31);
				z = xh * h + (z >>> 31);
				final int ret = (int) (x - z * mod);
				return ret >= mod ? ret - mod : ret;
			}
		}

		public static class BarrettSmall {
			private final int mod;
			final long t;

			BarrettSmall(final int mod) {
				this.mod = mod;
				t = (1L << 42) / mod;
			}

			int reduce(long x) {
				long q = x * t >> 42;
				x -= q * mod;
				return (int) (x >= mod ? x - mod : x);
			}
		}

		private static long safe_mod(long x, final long m) {
			x %= m;
			if (x < 0) x += m;
			return x;
		}

		private static long[] inv_gcd(long a, final long b) {
			a = safe_mod(a, b);
			if (a == 0) return new long[] { b, 0 };

			long s = b, t = a;
			long m0 = 0, m1 = 1;
			while (t > 0) {
				final long u = s / t;
				s -= t * u;
				m0 -= m1 * u;
				long tmp = s;
				s = t;
				t = tmp;
				tmp = m0;
				m0 = m1;
				m1 = tmp;
			}
			if (m0 < 0) m0 += b / s;
			return new long[] { s, m0 };
		}

		public static int pow(long n, long m, final int mod) {
			assert m >= 0 && mod >= 1;
			if (mod == 1) return 0;
			return pow(n, m, new Barrett(mod));
		}

		public static int pow(long n, long m, Barrett mod) {
			assert m >= 0;
			long ans = 1, num = n;
			while (m != 0) {
				if ((m & 1) != 0) ans = mod.reduce(ans * num);
				m >>>= 1;
				num = mod.reduce(num * num);
			}
			return (int) ans;
		}

		public static int pow998_244_353(long n, long m) {
			assert m >= 0;
			long ans = 1, num = n;
			while (m != 0) {
				if ((m & 1) != 0) ans = ans * num % 998_244_353;
				m >>>= 1;
				num = num * num % 998_244_353;
			}
			return (int) ans;
		}

		public static int pow754_974_721(long n, long m) {
			assert m >= 0;
			long ans = 1, num = n;
			while (m != 0) {
				if ((m & 1) != 0) ans = ans * num % 754_974_721;
				m >>>= 1;
				num = num * num % 754_974_721;
			}
			return (int) ans;
		}

		public static int pow167_772_161(long n, long m) {
			assert m >= 0;
			long ans = 1, num = n;
			while (m != 0) {
				if ((m & 1) != 0) ans = ans * num % 167_772_161;
				m >>>= 1;
				num = num * num % 167_772_161;
			}
			return (int) ans;
		}

		public static int pow469_762_049(long n, long m) {
			assert m >= 0;
			long ans = 1, num = n;
			while (m != 0) {
				if ((m & 1) != 0) ans = ans * num % 469_762_049;
				m >>>= 1;
				num = num * num % 469_762_049;
			}
			return (int) ans;
		}

		public static int pow1_000_000_007(long n, long m) {
			assert m >= 0;
			long ans = 1, num = n;
			while (m != 0) {
				if ((m & 1) != 0) ans = ans * num % 1_000_000_007;
				m >>>= 1;
				num = num * num % 1_000_000_007;
			}
			return (int) ans;
		}

		public static int pow(long n, long m, BarrettSmall mod) {
			assert m >= 0;
			long ans = 1, num = n;
			while (m != 0) {
				if ((m & 1) != 0) ans = mod.reduce(ans * num);
				m >>>= 1;
				num = mod.reduce(num * num);
			}
			return (int) ans;
		}

		public static long[] crt(final long[] r, final long[] m) {
			assert r.length == m.length;
			final int n = r.length;

			long r0 = 0, m0 = 1;
			for (int i = 0; i < n; i++) {
				assert 1 <= m[i];
				long r1 = safe_mod(r[i], m[i]), m1 = m[i];
				if (m0 < m1) {
					long tmp = r0;
					r0 = r1;
					r1 = tmp;
					tmp = m0;
					m0 = m1;
					m1 = tmp;
				}
				if (m0 % m1 == 0) {
					if (r0 % m1 != r1) return new long[] { 0, 0 };
					continue;
				}

				final long[] ig = inv_gcd(m0, m1);
				final long g = ig[0], im = ig[1];

				final long u1 = m1 / g;
				if ((r1 - r0) % g != 0) return new long[] { 0, 0 };

				final long x = (r1 - r0) / g % u1 * im % u1;

				r0 += x * m0;
				m0 *= u1;
				if (r0 < 0) r0 += m0;
				// System.err.printf("%d %d\n", r0, m0);
			}
			return new long[] { r0, m0 };
		}

		public static long floor_sum(final long n, final long m, long a, long b) {
			long ans = 0;
			if (a >= m) {
				ans += (n - 1) * n * (a / m) / 2;
				a %= m;
			}
			if (b >= m) {
				ans += n * (b / m);
				b %= m;
			}

			final long y_max = (a * n + b) / m;
			final long x_max = y_max * m - b;
			if (y_max == 0) return ans;
			ans += (n - (x_max + a - 1) / a) * y_max;
			ans += floor_sum(y_max, a, m, (a - x_max % a) % a);
			return ans;
		}
	}

	/**
	 * Convolution.
	 *
	 * @verified https://atcoder.jp/contests/practice2/tasks/practice2_f
	 * @verified https://judge.yosupo.jp/problem/convolution_mod_1000000007
	 */
	public static final class Convolution {
		/**
		 * writer: amotama 勝手に借りてます、問題あったらごめんね
		 */
		private static void fft(double[] a, double[] b, boolean invert) {
			int count = a.length;
			for (int i = 1, j = 0; i < count; i++) {
				int bit = count >> 1;
				for (; j >= bit; bit >>= 1) {
					j -= bit;
				}
				j += bit;
				if (i < j) {
					double temp = a[i];
					a[i] = a[j];
					a[j] = temp;
					temp = b[i];
					b[i] = b[j];
					b[j] = temp;
				}
			}
			for (int len = 2; len <= count; len <<= 1) {
				int halfLen = len >> 1;
				double angle = 2 * Math.PI / len;
				if (invert) {
					angle = -angle;
				}
				double wLenA = Math.cos(angle);
				double wLenB = Math.sin(angle);
				for (int i = 0; i < count; i += len) {
					double wA = 1;
					double wB = 0;
					for (int j = 0; j < halfLen; j++) {
						double uA = a[i + j];
						double uB = b[i + j];
						double vA = a[i + j + halfLen] * wA - b[i + j + halfLen] * wB;
						double vB = a[i + j + halfLen] * wB + b[i + j + halfLen] * wA;
						a[i + j] = uA + vA;
						b[i + j] = uB + vB;
						a[i + j + halfLen] = uA - vA;
						b[i + j + halfLen] = uB - vB;
						double nextWA = wA * wLenA - wB * wLenB;
						wB = wA * wLenB + wB * wLenA;
						wA = nextWA;
					}
				}
			}
			if (invert) {
				for (int i = 0; i < count; i++) {
					a[i] /= count;
					b[i] /= count;
				}
			}
		}

		/**
		 * writer: amotama 勝手に借りてます、問題あったらごめんね
		 */
		public static long[] convolution(long[] a, long[] b) {
			int resultSize = Integer.highestOneBit(Math.max(a.length, b.length) - 1) << 2;
			resultSize = Math.max(resultSize, 1);
			double[] aReal = new double[resultSize];
			double[] aImaginary = new double[resultSize];
			double[] bReal = new double[resultSize];
			double[] bImaginary = new double[resultSize];
			for (int i = 0; i < a.length; i++) aReal[i] = a[i];
			for (int i = 0; i < b.length; i++) bReal[i] = b[i];

			fft(aReal, aImaginary, false);
			if (a == b) {
				System.arraycopy(aReal, 0, bReal, 0, aReal.length);
				System.arraycopy(aImaginary, 0, bImaginary, 0, aImaginary.length);
			} else {
				fft(bReal, bImaginary, false);
			}
			for (int i = 0; i < resultSize; i++) {
				double real = aReal[i] * bReal[i] - aImaginary[i] * bImaginary[i];
				aImaginary[i] = aImaginary[i] * bReal[i] + bImaginary[i] * aReal[i];
				aReal[i] = real;
			}
			fft(aReal, aImaginary, true);
			long[] result = new long[a.length + b.length - 1];
			for (int i = 0; i < result.length; i++) result[i] = Math.round(aReal[i]);
			return result;
		}

		/**
		 * writer: amotama 勝手に借りてます、問題あったらごめんね
		 */
		public static int[] convolution(int[] a, int[] b) {
			int resultSize = Integer.highestOneBit(Math.max(a.length, b.length) - 1) << 2;
			resultSize = Math.max(resultSize, 1);
			double[] aReal = new double[resultSize];
			double[] aImaginary = new double[resultSize];
			double[] bReal = new double[resultSize];
			double[] bImaginary = new double[resultSize];
			for (int i = 0; i < a.length; i++) aReal[i] = a[i];
			for (int i = 0; i < b.length; i++) bReal[i] = b[i];
			fft(aReal, aImaginary, false);
			if (a == b) {
				System.arraycopy(aReal, 0, bReal, 0, aReal.length);
				System.arraycopy(aImaginary, 0, bImaginary, 0, aImaginary.length);
			} else {
				fft(bReal, bImaginary, false);
			}
			for (int i = 0; i < resultSize; i++) {
				double real = aReal[i] * bReal[i] - aImaginary[i] * bImaginary[i];
				aImaginary[i] = aImaginary[i] * bReal[i] + bImaginary[i] * aReal[i];
				aReal[i] = real;
			}
			fft(aReal, aImaginary, true);
			int[] result = new int[a.length + b.length - 1];
			for (int i = 0; i < result.length; i++) result[i] = (int) Math.round(aReal[i]);
			return result;
		}

		/**
		 * Find a primitive root.
		 *
		 * @param m A prime number.
		 * @return Primitive root.
		 */
		private static int primitiveRoot(final int m) {
			if (m == 2) return 1;
			if (m == 167772161) return 3;
			if (m == 469762049) return 3;
			if (m == 754974721) return 11;
			if (m == 998244353) return 3;

			final int[] divs = new int[20];
			divs[0] = 2;
			int cnt = 1;
			int x = (m - 1) / 2;
			while (x % 2 == 0) x /= 2;
			for (int i = 3; (long) i * i <= x; i += 2) {
				if (x % i == 0) {
					divs[cnt++] = i;
					while (x % i == 0) {
						x /= i;
					}
				}
			}
			if (x > 1) {
				divs[cnt++] = x;
			}
			for (int g = 2;; g++) {
				boolean ok = true;
				for (int i = 0; i < cnt; i++) {
					if (MathLib.pow(g, (m - 1) / divs[i], m) == 1) {
						ok = false;
						break;
					}
				}
				if (ok) return g;
			}
		}

		/**
		 * Ceil of power 2.
		 *
		 * @param n Value.
		 * @return Ceil of power 2.
		 */
		private static int ceilPow2(final int n) {
			int x = 0;
			while (1L << x < n) x++;
			return x;
		}

		/**
		 * Garner's algorithm.
		 *
		 * @param c    Mod convolution results.
		 * @param mods Mods.
		 * @return Result.
		 */
		private static long garner(final long[] c, final int[] mods) {
			final int n = c.length + 1;
			final long[] cnst = new long[n];
			final long[] coef = new long[n];
			java.util.Arrays.fill(coef, 1);
			for (int i = 0; i < n - 1; i++) {
				final int m1 = mods[i];
				long v = (c[i] - cnst[i] + m1) % m1;
				v = v * MathLib.pow(coef[i], m1 - 2, m1) % m1;

				for (int j = i + 1; j < n; j++) {
					final long m2 = mods[j];
					cnst[j] = (cnst[j] + coef[j] * v) % m2;
					coef[j] = coef[j] * m1 % m2;
				}
			}
			return cnst[n - 1];
		}

		/**
		 * Garner's algorithm.
		 *
		 * @param c    Mod convolution results.
		 * @param mods Mods.
		 * @return Result.
		 */
		private static int garner(int c0, int c1, int c2, final MathLib.Barrett[] mods) {
			final long[] cnst = new long[4];
			final long[] coef = new long[4];
			java.util.Arrays.fill(coef, 1);
			MathLib.Barrett m1 = mods[0];
			long v = m1.reduce(c0 - cnst[0] + m1.mod);
			v = m1.reduce(v * MathLib.pow(coef[0], m1.mod - 2, m1));
			{
				MathLib.Barrett m2 = mods[1];
				cnst[1] = m2.reduce(cnst[1] + coef[1] * v);
				coef[1] = m2.reduce(coef[1] * m1.mod);
				m2 = mods[2];
				cnst[2] = m2.reduce(cnst[2] + coef[2] * v);
				coef[2] = m2.reduce(coef[2] * m1.mod);
				m2 = mods[3];
				cnst[3] = m2.reduce(cnst[3] + coef[3] * v);
				coef[3] = m2.reduce(coef[3] * m1.mod);
			}
			m1 = mods[1];
			v = m1.reduce(c1 - cnst[1] + m1.mod);
			v = m1.reduce(v * MathLib.pow(coef[1], m1.mod - 2, m1));
			{
				MathLib.Barrett m2 = mods[2];
				cnst[2] = m2.reduce(cnst[2] + coef[2] * v);
				coef[2] = m2.reduce(coef[2] * m1.mod);
				m2 = mods[3];
				cnst[3] = m2.reduce(cnst[3] + coef[3] * v);
				coef[3] = m2.reduce(coef[3] * m1.mod);
			}
			m1 = mods[2];
			v = m1.reduce(c2 - cnst[2] + m1.mod);
			v = m1.reduce(v * MathLib.pow(coef[2], m1.mod - 2, m1));
			{
				MathLib.Barrett m2 = mods[3];
				cnst[3] = m2.reduce(cnst[3] + coef[3] * v);
				coef[3] = m2.reduce(coef[3] * m1.mod);
			}
			return (int) cnst[3];
		}

		/**
		 * Garner's algorithm.
		 *
		 * @param c    Mod convolution results.
		 * @param mods Mods.
		 * @return Result.
		 */
		private static int garner1_000_000_007(int c0, int c1, int c2) {
			final long[] cnst = new long[4];
			final long[] coef = new long[4];
			java.util.Arrays.fill(coef, 1);
			long v = (c0 - cnst[0] + 754_974_721) % 754_974_721;
			v = v * MathLib.pow754_974_721(coef[0], 754_974_721 - 2) % 754_974_721;
			{
				cnst[1] = (cnst[1] + coef[1] * v) % 167_772_161;
				coef[1] = coef[1] * 754_974_721 % 167_772_161;
				cnst[2] = (cnst[2] + coef[2] * v) % 469_762_049;
				coef[2] = coef[2] * 754_974_721 % 469_762_049;
				cnst[3] = (cnst[3] + coef[3] * v) % 1_000_000_007;
				coef[3] = coef[3] * 754_974_721 % 1_000_000_007;
			}
			v = (c1 - cnst[1] + 167_772_161) % 167_772_161;
			v = v * MathLib.pow167_772_161(coef[1], 167_772_161 - 2) % 167_772_161;
			{
				cnst[2] = (cnst[2] + coef[2] * v) % 469_762_049;
				coef[2] = coef[2] * 167_772_161 % 469_762_049;
				cnst[3] = (cnst[3] + coef[3] * v) % 1_000_000_007;
				coef[3] = coef[3] * 167_772_161 % 1_000_000_007;
			}
			v = (c2 - cnst[2] + 469_762_049) % 469_762_049;
			v = v * MathLib.pow469_762_049(coef[2], 469_762_049 - 2) % 469_762_049;
			{
				cnst[3] = (cnst[3] + coef[3] * v) % 1_000_000_007;
				coef[3] = coef[3] * 469_762_049 % 1_000_000_007;
			}
			return (int) cnst[3];
		}

		/**
		 * Pre-calculation for NTT.
		 *
		 * @param mod NTT Prime.
		 * @param g   Primitive root of mod.
		 * @return Pre-calculation table.
		 */
		private static long[] sumE(final int mod, final int g) {
			final long[] sum_e = new long[30];
			final long[] es = new long[30];
			final long[] ies = new long[30];
			final int cnt2 = Integer.numberOfTrailingZeros(mod - 1);
			long e = MathLib.pow(g, mod - 1 >> cnt2, mod);
			long ie = MathLib.pow(e, mod - 2, mod);
			for (int i = cnt2; i >= 2; i--) {
				es[i - 2] = e;
				ies[i - 2] = ie;
				e = e * e % mod;
				ie = ie * ie % mod;
			}
			long now = 1;
			for (int i = 0; i < cnt2 - 2; i++) {
				sum_e[i] = es[i] * now % mod;
				now = now * ies[i] % mod;
			}
			return sum_e;
		}

		/**
		 * Pre-calculation for inverse NTT.
		 *
		 * @param mod Mod.
		 * @param g   Primitive root of mod.
		 * @return Pre-calculation table.
		 */
		private static long[] sumIE(final int mod, final int g) {
			final long[] sum_ie = new long[30];
			final long[] es = new long[30];
			final long[] ies = new long[30];

			final int cnt2 = Integer.numberOfTrailingZeros(mod - 1);
			long e = MathLib.pow(g, mod - 1 >> cnt2, mod);
			long ie = MathLib.pow(e, mod - 2, mod);
			for (int i = cnt2; i >= 2; i--) {
				es[i - 2] = e;
				ies[i - 2] = ie;
				e = e * e % mod;
				ie = ie * ie % mod;
			}
			long now = 1;
			for (int i = 0; i < cnt2 - 2; i++) {
				sum_ie[i] = ies[i] * now % mod;
				now = now * es[i] % mod;
			}
			return sum_ie;
		}

		/**
		 * Inverse NTT.
		 *
		 * @param a     Target array.
		 * @param sumIE Pre-calculation table.
		 * @param mod   NTT Prime.
		 */
		private static void butterflyInv(final long[] a, final long[] sumIE, final int mod) {
			final int n = a.length;
			final int h = ceilPow2(n);

			for (int ph = h; ph >= 1; ph--) {
				final int w = 1 << ph - 1, p = 1 << h - ph;
				long inow = 1;
				for (int s = 0; s < w; s++) {
					final int offset = s << h - ph + 1;
					for (int i = 0; i < p; i++) {
						final long l = a[i + offset];
						final long r = a[i + offset + p];
						a[i + offset] = (l + r) % mod;
						a[i + offset + p] = (mod + l - r) * inow % mod;
					}
					final int x = Integer.numberOfTrailingZeros(~s);
					inow = inow * sumIE[x] % mod;
				}
			}
		}

		/**
		 * Inverse NTT.
		 *
		 * @param a    Target array.
		 * @param sumE Pre-calculation table.
		 * @param mod  NTT Prime.
		 */
		private static void butterfly(final long[] a, final long[] sumE, final int mod) {
			final int n = a.length;
			final int h = ceilPow2(n);

			for (int ph = 1; ph <= h; ph++) {
				final int w = 1 << ph - 1, p = 1 << h - ph;
				long now = 1;
				for (int s = 0; s < w; s++) {
					final int offset = s << h - ph + 1;
					for (int i = 0; i < p; i++) {
						final long l = a[i + offset];
						final long r = a[i + offset + p] * now % mod;
						a[i + offset] = (l + r) % mod;
						a[i + offset + p] = (l - r + mod) % mod;
					}
					final int x = Integer.numberOfTrailingZeros(~s);
					now = now * sumE[x] % mod;
				}
			}
		}

		/**
		 * Inverse NTT used mod 998_244_353.
		 *
		 * @param a     Target array.
		 * @param sumIE Pre-calculation table.
		 */
		private static void butterflyInv998_244_353(final int[] a, final int[] sumIE) {
			final int n = a.length;
			final int h = ceilPow2(n);

			for (int ph = h; ph >= 1; ph--) {
				final int w = 1 << ph - 1, p = 1 << h - ph;
				long inow = 1;
				for (int s = 0; s < w; s++) {
					final int offset = s << h - ph + 1;
					for (int i = 0; i < p; i++) {
						final long l = a[i + offset];
						final long r = a[i + offset + p];
						a[i + offset] = (int)((l + r) % 998_244_353);
						a[i + offset + p] = (int)((998_244_353 + l - r) * inow % 998_244_353);
					}
					final int x = Integer.numberOfTrailingZeros(~s);
					inow = inow * sumIE[x] % 998_244_353;
				}
			}
		}

		/**
		 * Inverse NTT used mod 754_974_721.
		 *
		 * @param a     Target array.
		 * @param sumIE Pre-calculation table.
		 */
		private static void butterflyInv754_974_721(final int[] a, final int[] sumIE) {
			final int n = a.length;
			final int h = ceilPow2(n);

			for (int ph = h; ph >= 1; ph--) {
				final int w = 1 << ph - 1, p = 1 << h - ph;
				long inow = 1;
				for (int s = 0; s < w; s++) {
					final int offset = s << h - ph + 1;
					for (int i = 0; i < p; i++) {
						final long l = a[i + offset];
						final long r = a[i + offset + p];
						a[i + offset] = (int)((l + r) % 754_974_721);
						a[i + offset + p] = (int)((754_974_721 + l - r) * inow % 754_974_721);
					}
					final int x = Integer.numberOfTrailingZeros(~s);
					inow = inow * sumIE[x] % 754_974_721;
				}
			}
		}

		/**
		 * Inverse NTT used mod 167_772_161.
		 *
		 * @param a     Target array.
		 * @param sumIE Pre-calculation table.
		 */
		private static void butterflyInv167_772_161(final int[] a, final int[] sumIE) {
			final int n = a.length;
			final int h = ceilPow2(n);

			for (int ph = h; ph >= 1; ph--) {
				final int w = 1 << ph - 1, p = 1 << h - ph;
				long inow = 1;
				for (int s = 0; s < w; s++) {
					final int offset = s << h - ph + 1;
					for (int i = 0; i < p; i++) {
						final long l = a[i + offset];
						final long r = a[i + offset + p];
						a[i + offset] = (int)((l + r) % 167_772_161);
						a[i + offset + p] = (int)((167_772_161 + l - r) * inow % 167_772_161);
					}
					final int x = Integer.numberOfTrailingZeros(~s);
					inow = inow * sumIE[x] % 167_772_161;
				}
			}
		}

		/**
		 * Inverse NTT used mod 469_762_049.
		 *
		 * @param a     Target array.
		 * @param sumIE Pre-calculation table.
		 */
		private static void butterflyInv469_762_049(final int[] a, final int[] sumIE) {
			final int n = a.length;
			final int h = ceilPow2(n);

			for (int ph = h; ph >= 1; ph--) {
				final int w = 1 << ph - 1, p = 1 << h - ph;
				long inow = 1;
				for (int s = 0; s < w; s++) {
					final int offset = s << h - ph + 1;
					for (int i = 0; i < p; i++) {
						final long l = a[i + offset];
						final long r = a[i + offset + p];
						a[i + offset] = (int)((l + r) % 469_762_049);
						a[i + offset + p] = (int)((469_762_049 + l - r) * inow % 469_762_049);
					}
					final int x = Integer.numberOfTrailingZeros(~s);
					inow = inow * sumIE[x] % 469_762_049;
				}
			}
		}

		/**
		 * Inverse NTT.
		 *
		 * @param a     Target array.
		 * @param sumIE Pre-calculation table.
		 * @param mod   NTT Prime.
		 */
		private static void butterflyInv(final int[] a, final int[] sumIE, final MathLib.Barrett mod) {
			final int n = a.length;
			final int h = ceilPow2(n);

			for (int ph = h; ph >= 1; ph--) {
				final int w = 1 << ph - 1, p = 1 << h - ph;
				long inow = 1;
				for (int s = 0; s < w; s++) {
					final int offset = s << h - ph + 1;
					for (int i = 0; i < p; i++) {
						final long l = a[i + offset];
						final long r = a[i + offset + p];
						long sum = l + r;
						if (sum >= mod.mod) sum -= mod.mod;
						a[i + offset] = (int)sum;
						a[i + offset + p] = mod.reduce((mod.mod + l - r) * inow);
					}
					final int x = Integer.numberOfTrailingZeros(~s);
					inow = mod.reduce(inow * sumIE[x]);
				}
			}
		}

		/**
		 * Inverse NTT used mod 998_244_353.
		 *
		 * @param a    Target array.
		 * @param sumE Pre-calculation table.
		 * @param mod  NTT Prime.
		 */
		private static void butterfly998_244_353(final int[] a, final int[] sumE) {
			final int n = a.length;
			final int h = ceilPow2(n);
			final long ADD = (long)(998_244_353 - 2) * 998_244_353;

			for (int ph = 1; ph <= h; ph++) {
				final int w = 1 << ph - 1, p = 1 << h - ph;
				long now = 1;
				for (int s = 0; s < w; s++) {
					final int offset = s << h - ph + 1;
					for (int i = 0; i < p; i++) {
						final long l = a[i + offset];
						final long r = a[i + offset + p] * now;
						a[i + offset] = (int)((l + r) % 998_244_353);
						a[i + offset + p] = (int)((l - r + ADD) % 998_244_353);
					}
					final int x = Integer.numberOfTrailingZeros(~s);
					now = now * sumE[x] % 998_244_353;
				}
			}
		}

		/**
		 * Inverse NTT used mod 754_974_721.
		 *
		 * @param a    Target array.
		 * @param sumE Pre-calculation table.
		 * @param mod  NTT Prime.
		 */
		private static void butterfly754_974_721(final int[] a, final int[] sumE) {
			final int n = a.length;
			final int h = ceilPow2(n);
			final long ADD = (long)(754_974_721 - 2) * 754_974_721;

			for (int ph = 1; ph <= h; ph++) {
				final int w = 1 << ph - 1, p = 1 << h - ph;
				long now = 1;
				for (int s = 0; s < w; s++) {
					final int offset = s << h - ph + 1;
					for (int i = 0; i < p; i++) {
						final long l = a[i + offset];
						final long r = a[i + offset + p] * now;
						a[i + offset] = (int)((l + r) % 754_974_721);
						a[i + offset + p] = (int)((l - r + ADD) % 754_974_721);
					}
					final int x = Integer.numberOfTrailingZeros(~s);
					now = now * sumE[x] % 754_974_721;
				}
			}
		}

		/**
		 * Inverse NTT used mod 167_772_161.
		 *
		 * @param a    Target array.
		 * @param sumE Pre-calculation table.
		 * @param mod  NTT Prime.
		 */
		private static void butterfly167_772_161(final int[] a, final int[] sumE) {
			final int n = a.length;
			final int h = ceilPow2(n);
			final long ADD = (long)(167_772_161 - 2) * 167_772_161;

			for (int ph = 1; ph <= h; ph++) {
				final int w = 1 << ph - 1, p = 1 << h - ph;
				long now = 1;
				for (int s = 0; s < w; s++) {
					final int offset = s << h - ph + 1;
					for (int i = 0; i < p; i++) {
						final long l = a[i + offset];
						final long r = a[i + offset + p] * now;
						a[i + offset] = (int)((l + r) % 167_772_161);
						a[i + offset + p] = (int)((l - r + ADD) % 167_772_161);
					}
					final int x = Integer.numberOfTrailingZeros(~s);
					now = now * sumE[x] % 167_772_161;
				}
			}
		}

		/**
		 * Inverse NTT used mod 469_762_049.
		 *
		 * @param a    Target array.
		 * @param sumE Pre-calculation table.
		 * @param mod  NTT Prime.
		 */
		private static void butterfly469_762_049(final int[] a, final int[] sumE) {
			final int n = a.length;
			final int h = ceilPow2(n);
			final long ADD = (long)(469_762_049 - 2) * 469_762_049;

			for (int ph = 1; ph <= h; ph++) {
				final int w = 1 << ph - 1, p = 1 << h - ph;
				long now = 1;
				for (int s = 0; s < w; s++) {
					final int offset = s << h - ph + 1;
					for (int i = 0; i < p; i++) {
						final long l = a[i + offset];
						final long r = a[i + offset + p] * now;
						a[i + offset] = (int)((l + r) % 469_762_049);
						a[i + offset + p] = (int)((l - r + ADD) % 469_762_049);
					}
					final int x = Integer.numberOfTrailingZeros(~s);
					now = now * sumE[x] % 469_762_049;
				}
			}
		}

		/**
		 * Inverse NTT.
		 *
		 * @param a    Target array.
		 * @param sumE Pre-calculation table.
		 * @param mod  NTT Prime.
		 */
		private static void butterfly(final int[] a, final int[] sumE, final MathLib.Barrett mod) {
			final int n = a.length;
			final int h = ceilPow2(n);
			final long ADD = (long)(mod.mod - 2) * mod.mod;

			for (int ph = 1; ph <= h; ph++) {
				final int w = 1 << ph - 1, p = 1 << h - ph;
				long now = 1;
				for (int s = 0; s < w; s++) {
					final int offset = s << h - ph + 1;
					for (int i = 0; i < p; i++) {
						final long l = a[i + offset];
						final long r = a[i + offset + p] * now;
						a[i + offset] = mod.reduce(l + r);
						a[i + offset + p] = mod.reduce(l - r + ADD);
					}
					final int x = Integer.numberOfTrailingZeros(~s);
					now = mod.reduce(now * sumE[x]);
				}
			}
		}

		/**
		 * Convolution used mod 998_244_353.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @return Answer.
		 */
		public static int[] convolution998_244_353(int[] a, int[] b) {
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new int[0];

			final int z = 1 << ceilPow2(n + m - 1);
			{
				final int[] na = new int[z];
				final int[] nb = new int[z];
				System.arraycopy(a, 0, na, 0, n);
				System.arraycopy(b, 0, nb, 0, m);
				a = na;
				b = nb;
			}

			final int g = primitiveRoot(998_244_353);
			final int[] sume;
			{
				long[] s = sumE(998_244_353, g);
				sume = new int[s.length];
				for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
			}
			final int[] sumie;
			{
				long[] s = sumIE(998_244_353, g);
				sumie = new int[s.length];
				for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
			}

			butterfly998_244_353(a, sume);
			butterfly998_244_353(b, sume);
			for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 998_244_353);
			butterflyInv998_244_353(a, sumie);
			a = java.util.Arrays.copyOf(a, n + m - 1);

			final long iz = MathLib.pow998_244_353(z, 998_244_353 - 2);
			for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 998_244_353);
			return a;
		}

		/**
		 * Convolution used mod 754_974_721.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @return Answer.
		 */
		public static int[] convolution754_974_721(int[] a, int[] b) {
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new int[0];

			final int z = 1 << ceilPow2(n + m - 1);
			{
				final int[] na = new int[z];
				final int[] nb = new int[z];
				System.arraycopy(a, 0, na, 0, n);
				System.arraycopy(b, 0, nb, 0, m);
				a = na;
				b = nb;
			}

			final int g = primitiveRoot(754_974_721);
			final int[] sume;
			{
				long[] s = sumE(754_974_721, g);
				sume = new int[s.length];
				for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
			}
			final int[] sumie;
			{
				long[] s = sumIE(754_974_721, g);
				sumie = new int[s.length];
				for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
			}

			butterfly754_974_721(a, sume);
			butterfly754_974_721(b, sume);
			for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 754_974_721);
			butterflyInv754_974_721(a, sumie);
			a = java.util.Arrays.copyOf(a, n + m - 1);

			final long iz = MathLib.pow754_974_721(z, 754_974_721 - 2);
			for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 754_974_721);
			return a;
		}

		/**
		 * Convolution used mod 167_772_161.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @return Answer.
		 */
		public static int[] convolution167_772_161(int[] a, int[] b) {
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new int[0];

			final int z = 1 << ceilPow2(n + m - 1);
			{
				final int[] na = new int[z];
				final int[] nb = new int[z];
				System.arraycopy(a, 0, na, 0, n);
				System.arraycopy(b, 0, nb, 0, m);
				a = na;
				b = nb;
			}

			final int g = primitiveRoot(167_772_161);
			final int[] sume;
			{
				long[] s = sumE(167_772_161, g);
				sume = new int[s.length];
				for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
			}
			final int[] sumie;
			{
				long[] s = sumIE(167_772_161, g);
				sumie = new int[s.length];
				for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
			}

			butterfly167_772_161(a, sume);
			butterfly167_772_161(b, sume);
			for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 167_772_161);
			butterflyInv167_772_161(a, sumie);
			a = java.util.Arrays.copyOf(a, n + m - 1);

			final long iz = MathLib.pow167_772_161(z, 167_772_161 - 2);
			for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 167_772_161);
			return a;
		}

		/**
		 * Convolution used mod 469_762_049.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @return Answer.
		 */
		public static int[] convolution469_762_049(int[] a, int[] b) {
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new int[0];

			final int z = 1 << ceilPow2(n + m - 1);
			{
				final int[] na = new int[z];
				final int[] nb = new int[z];
				System.arraycopy(a, 0, na, 0, n);
				System.arraycopy(b, 0, nb, 0, m);
				a = na;
				b = nb;
			}

			final int g = primitiveRoot(469_762_049);
			final int[] sume;
			{
				long[] s = sumE(469_762_049, g);
				sume = new int[s.length];
				for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
			}
			final int[] sumie;
			{
				long[] s = sumIE(469_762_049, g);
				sumie = new int[s.length];
				for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
			}

			butterfly469_762_049(a, sume);
			butterfly469_762_049(b, sume);
			for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 469_762_049);
			butterflyInv469_762_049(a, sumie);
			a = java.util.Arrays.copyOf(a, n + m - 1);

			final long iz = MathLib.pow469_762_049(z, 469_762_049 - 2);
			for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 469_762_049);
			return a;
		}

		/**
		 * Convolution.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @param mod NTT Prime.
		 * @return Answer.
		 */
		public static int[] convolution(int[] a, int[] b, final int mod) {
			MathLib.Barrett barrett = new MathLib.Barrett(mod);
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new int[0];

			final int z = 1 << ceilPow2(n + m - 1);
			{
				final int[] na = new int[z];
				final int[] nb = new int[z];
				System.arraycopy(a, 0, na, 0, n);
				System.arraycopy(b, 0, nb, 0, m);
				a = na;
				b = nb;
			}

			final int g = primitiveRoot(mod);
			final int[] sume;
			{
				long[] s = sumE(mod, g);
				sume = new int[s.length];
				for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
			}
			final int[] sumie;
			{
				long[] s = sumIE(mod, g);
				sumie = new int[s.length];
				for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
			}

			butterfly(a, sume, barrett);
			butterfly(b, sume, barrett);
			for (int i = 0; i < z; i++) a[i] = barrett.reduce((long) a[i] * b[i]);
			butterflyInv(a, sumie, barrett);
			a = java.util.Arrays.copyOf(a, n + m - 1);

			final long iz = MathLib.pow(z, mod - 2, mod);
			for (int i = 0; i < n + m - 1; i++) a[i] = barrett.reduce(a[i] * iz);
			return a;
		}

		/**
		 * Convolution.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @param mod NTT Prime.
		 * @return Answer.
		 */
		public static long[] convolution(long[] a, long[] b, final int mod) {
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new long[0];

			final int z = 1 << ceilPow2(n + m - 1);
			{
				final long[] na = new long[z];
				final long[] nb = new long[z];
				System.arraycopy(a, 0, na, 0, n);
				System.arraycopy(b, 0, nb, 0, m);
				a = na;
				b = nb;
			}

			final int g = primitiveRoot(mod);
			final long[] sume = sumE(mod, g);
			final long[] sumie = sumIE(mod, g);

			butterfly(a, sume, mod);
			butterfly(b, sume, mod);
			for (int i = 0; i < z; i++) {
				a[i] = a[i] * b[i] % mod;
			}
			butterflyInv(a, sumie, mod);
			a = java.util.Arrays.copyOf(a, n + m - 1);

			final long iz = MathLib.pow(z, mod - 2, mod);
			for (int i = 0; i < n + m - 1; i++) a[i] = a[i] * iz % mod;
			return a;
		}

		/**
		 * Convolution.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @param mod Any mod.
		 * @return Answer.
		 */
		public static long[] convolutionLL(final long[] a, final long[] b, final int mod) {
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new long[0];

			final int mod1 = 754_974_721;
			final int mod2 = 167_772_161;
			final int mod3 = 469_762_049;

			final long[] c1 = convolution(a, b, mod1);
			final long[] c2 = convolution(a, b, mod2);
			final long[] c3 = convolution(a, b, mod3);

			final int retSize = c1.length;
			final long[] ret = new long[retSize];
			final int[] mods = { mod1, mod2, mod3, mod };
			for (int i = 0; i < retSize; ++i) {
				ret[i] = garner(new long[] { c1[i], c2[i], c3[i] }, mods);
			}
			return ret;
		}

		/**
		 * Convolution.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @param mod Any mod.
		 * @return Answer.
		 */
		public static int[] convolutionLL(final int[] a, final int[] b, final int mod) {
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new int[0];

			final int mod1 = 754_974_721;
			final int mod2 = 167_772_161;
			final int mod3 = 469_762_049;

			final int[] c1 = convolution754_974_721(a, b);
			final int[] c2 = convolution167_772_161(a, b);
			final int[] c3 = convolution469_762_049(a, b);

			final int retSize = c1.length;
			final int[] ret = new int[retSize];
			final MathLib.Barrett[] mods = { new MathLib.Barrett(mod1), new MathLib.Barrett(mod2),
					new MathLib.Barrett(mod3), new MathLib.Barrett(mod) };
			for (int i = 0; i < retSize; ++i) ret[i] = garner(c1[i], c2[i], c3[i], mods);
			return ret;
		}

		/**
		 * Convolution used mod 1_000_000_007.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @return Answer.
		 */
		public static int[] convolution1_000_000_007(final int[] a, final int[] b) {
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new int[0];

			final int[] c1 = convolution754_974_721(a, b);
			final int[] c2 = convolution167_772_161(a, b);
			final int[] c3 = convolution469_762_049(a, b);

			final int retSize = c1.length;
			final int[] ret = new int[retSize];
			for (int i = 0; i < retSize; ++i) ret[i] = garner1_000_000_007(c1[i], c2[i], c3[i]);
			return ret;
		}

		/**
		 * Convolution. need: length < 2000
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @param mod Any mod.
		 * @return Answer.
		 */
		public static int[] convolutionLL2(final int[] a, final int[] b, final int mod) {
			if (Math.max(a.length, b.length) < 4000) {
				long[] la = new long[a.length], ha = new long[a.length], ma = new long[a.length], lb = new long[b.length],
						hb = new long[b.length], mb = new long[b.length];
				MathLib.Barrett barrett = new MathLib.Barrett(mod);
				for (int i = 0; i < a.length; ++i) {
					ha[i] = a[i] >> 15;
					la[i] = a[i] & 0x7FFF;
					ma[i] = la[i] + ha[i];
				}
				for (int i = 0; i < b.length; ++i) {
					hb[i] = b[i] >> 15;
					lb[i] = b[i] & 0x7FFF;
					mb[i] = lb[i] + hb[i];
				}
				long[] l = convolution(la, lb), h = convolution(ha, hb), m = convolution(ma, mb);
				int[] ret = new int[m.length];
				for (int i = 0; i < m.length; ++i) {
					h[i] = barrett.reduce(h[i]);
					m[i] = barrett.reduce(m[i] - l[i] - h[i] + (long)m.length * mod);
					ret[i] = barrett.reduce((h[i] << 30) + (m[i] << 15) + l[i]);
				}
				return ret;
			}
			return convolutionLL(a, b, mod);
		}

		/**
		 * Naive convolution. (Complexity is O(N^2)!!)
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @param mod Mod.
		 * @return Answer.
		 */
		public static long[] convolutionNaive(final long[] a, final long[] b, final int mod) {
			final int n = a.length;
			final int m = b.length;
			final int k = n + m - 1;
			final long[] ret = new long[k];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					ret[i + j] += a[i] * b[j] % mod;
					ret[i + j] %= mod;
				}
			}
			return ret;
		}
	}
}

class FastScanner {

	private final java.io.InputStream in = System.in;
	private final byte[] buffer = new byte[8192];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) return true;
		ptr = 0;
		try {
			buflen = in.read(buffer);
		} catch (java.io.IOException e) {
			e.printStackTrace();
		}
		return buflen > 0;
	}

	private byte readByte() {
		return hasNextByte() ? buffer[ptr++] : -1;
	}

	private static boolean isPrintableChar(byte c) {
		return 32 < c || c < 0;
	}

	private static boolean isNumber(int c) {
		return '0' <= c && c <= '9';
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext()) throw new java.util.NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		byte b;
		while (isPrintableChar(b = readByte())) sb.appendCodePoint(b);
		return sb.toString();
	}

	public final char nextChar() {
		if (!hasNext()) throw new java.util.NoSuchElementException();
		return (char) readByte();
	}

	public final long nextLong() {
		if (!hasNext()) throw new java.util.NoSuchElementException();
		long n = 0;
		try {
			byte b = readByte();
			if (b == '-') {
				while (isNumber(b = readByte())) n = n * 10 + '0' - b;
				return n;
			} else if (!isNumber(b)) throw new NumberFormatException();
			do n = n * 10 + b - '0'; while (isNumber(b = readByte()));
		} catch (java.util.NoSuchElementException e) {}
		return n;
	}

	public final int nextInt() {
		if (!hasNext()) throw new java.util.NoSuchElementException();
		int n = 0;
		try {
			byte b = readByte();
			if (b == '-') {
				while (isNumber(b = readByte())) n = n * 10 + '0' - b;
				return n;
			} else if (!isNumber(b)) throw new NumberFormatException();
			do n = n * 10 + b - '0'; while (isNumber(b = readByte()));
		} catch (java.util.NoSuchElementException e) {}
		return n;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

class Arrays {

	public static void sort(final int[] array) {
		sort(array, 0, array.length);
	}

	public static void sort(final int[] array, int fromIndex, int toIndex) {
		if (toIndex - fromIndex <= 512) {
			java.util.Arrays.sort(array, fromIndex, toIndex);
			return;
		}
		sort(array, fromIndex, toIndex, 0, new int[array.length]);
	}

	private static final void sort(int[] a, final int from, final int to, final int l, final int[] bucket) {
		if (to - from <= 512) {
			java.util.Arrays.sort(a, from, to);
			return;
		}
		final int BUCKET_SIZE = 256;
		final int INT_RECURSION = 4;
		final int MASK = 0xff;
		final int shift = l << 3;
		final int[] cnt = new int[BUCKET_SIZE + 1];
		final int[] put = new int[BUCKET_SIZE];
		for (int i = from; i < to; i++) ++cnt[(a[i] >>> shift & MASK) + 1];
		for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i];
		for (int i = from; i < to; i++) {
			int bi = a[i] >>> shift & MASK;
			bucket[cnt[bi] + put[bi]++] = a[i];
		}
		for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) {
			int begin = cnt[i];
			int len = cnt[i + 1] - begin;
			System.arraycopy(bucket, begin, a, idx, len);
			idx += len;
		}
		final int nxtL = l + 1;
		if (nxtL < INT_RECURSION) {
			sort(a, from, to, nxtL, bucket);
			if (l == 0) {
				int lft, rgt;
				lft = from - 1;
				rgt = to;
				while (rgt - lft > 1) {
					int mid = lft + rgt >> 1;
					if (a[mid] < 0) lft = mid;
					else rgt = mid;
				}
				reverse(a, from, rgt);
				reverse(a, rgt, to);
			}
		}
	}

	public static void sort(final long[] array) {
		sort(array, 0, array.length);
	}

	public static void sort(final long[] array, int fromIndex, int toIndex) {
		if (toIndex - fromIndex <= 512) {
			java.util.Arrays.sort(array, fromIndex, toIndex);
			return;
		}
		sort(array, fromIndex, toIndex, 0, new long[array.length]);
	}

	private static final void sort(long[] a, final int from, final int to, final int l, final long[] bucket) {
		final int BUCKET_SIZE = 256;
		final int LONG_RECURSION = 8;
		final int MASK = 0xff;
		final int shift = l << 3;
		final int[] cnt = new int[BUCKET_SIZE + 1];
		final int[] put = new int[BUCKET_SIZE];
		for (int i = from; i < to; i++) ++cnt[(int) ((a[i] >>> shift & MASK) + 1)];
		for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i];
		for (int i = from; i < to; i++) {
			int bi = (int) (a[i] >>> shift & MASK);
			bucket[cnt[bi] + put[bi]++] = a[i];
		}
		for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) {
			int begin = cnt[i];
			int len = cnt[i + 1] - begin;
			System.arraycopy(bucket, begin, a, idx, len);
			idx += len;
		}
		final int nxtL = l + 1;
		if (nxtL < LONG_RECURSION) {
			sort(a, from, to, nxtL, bucket);
			if (l == 0) {
				int lft, rgt;
				lft = from - 1;
				rgt = to;
				while (rgt - lft > 1) {
					int mid = lft + rgt >> 1;
					if (a[mid] < 0) lft = mid;
					else rgt = mid;
				}
				reverse(a, from, rgt);
				reverse(a, rgt, to);
			}
		}
	}

	public static void reverse(int[] array) {
		reverse(array, 0, array.length);
	}

	public static void reverse(int[] array, int fromIndex, int toIndex) {
		for (--toIndex; fromIndex < toIndex; ++fromIndex, --toIndex) {
			int swap = array[fromIndex];
			array[fromIndex] = array[toIndex];
			array[toIndex] = swap;
		}
	}

	public static void reverse(long[] array) {
		reverse(array, 0, array.length);
	}

	public static void reverse(long[] array, int fromIndex, int toIndex) {
		for (--toIndex; fromIndex < toIndex; ++fromIndex, --toIndex) {
			long swap = array[fromIndex];
			array[fromIndex] = array[toIndex];
			array[toIndex] = swap;
		}
	}

	public static void shuffle(int[] array) {
		java.util.Random rnd = new java.util.Random();
		for (int i = 0; i < array.length; ++i) {
			int j = rnd.nextInt(array.length - i) + i;
			int swap = array[i];
			array[i] = array[j];
			array[j] = swap;
		}
	}

	public static void shuffle(long[] array) {
		java.util.Random rnd = new java.util.Random();
		for (int i = 0; i < array.length; ++i) {
			int j = rnd.nextInt(array.length - i) + i;
			long swap = array[i];
			array[i] = array[j];
			array[j] = swap;
		}
	}
}

class IntMath {

	public static int gcd(int a, int b) {
		while (a != 0) if ((b %= a) != 0) a %= b;
		else return a;
		return b;
	}

	public static int gcd(int... array) {
		int ret = array[0];
		for (int i = 1; i < array.length; ++i) ret = gcd(ret, array[i]);
		return ret;
	}

	public static long gcd(long a, long b) {
		while (a != 0) if ((b %= a) != 0) a %= b;
		else return a;
		return b;
	}

	public static long gcd(long... array) {
		long ret = array[0];
		for (int i = 1; i < array.length; ++i) ret = gcd(ret, array[i]);
		return ret;
	}

	public static long lcm(long a, long b) {
		return a / gcd(a, b) * b;
	}

	public static int pow(int a, int b) {
		int ans = 1;
		for (int mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;
		return ans;
	}

	public static long pow(long a, long b) {
		long ans = 1;
		for (long mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;
		return ans;
	}

	public static int pow(int a, long b, int mod) {
		if (b < 0) b = b % (mod - 1) + mod - 1;
		long ans = 1;
		for (long mul = a; b > 0; b >>= 1, mul = mul * mul % mod) if ((b & 1) != 0) ans = ans * mul % mod;
		return (int) ans;
	}

	public static int pow(long a, long b, int mod) {
		return pow((int) (a % mod), b, mod);
	}

	public static int floorsqrt(long n) {
		return (int) Math.sqrt(n + 0.1);
	}

	public static int ceilsqrt(long n) {
		return n <= 1 ? (int) n : (int) Math.sqrt(n - 0.1) + 1;
	}
}