#include<bits/stdc++.h>
using namespace std;

int main() {
	int t; cin >> t;
	while (t--) {
		int k; cin >> k;
		cout << 100 / gcd(100, k) << endl;
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for (int &x : a) scanf("%d", &x);
    int ans = 2;
    if (is_sorted(a.begin(), a.end()))
      ans = 0;
    else if (a[0] == 1 || a[n - 1] == n)
      ans = 1;
    else if (a[0] == n && a[n - 1] == 1)
      ans = 3;
    printf("%d\n", ans);
  }
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

struct bot{
	int x, d;
};

int main() {
	int t;
	cin >> t;
	forn(_, t){
		int n, m;
		scanf("%d%d", &n, &m);
		vector<bot> a(n);
		forn(i, n) scanf("%d", &a[i].x);
		forn(i, n){
			char c;
			scanf(" %c", &c);
			a[i].d = c == 'L' ? -1 : 1;
		}
		vector<int> ord(n);
		iota(ord.begin(), ord.end(), 0);
		sort(ord.begin(), ord.end(), [&a](int x, int y){
			return a[x].x < a[y].x;
		});
		vector<int> ans(n, -1);
		vector<vector<int>> par(2);
		for (int i : ord){
			int p = a[i].x % 2;
			if (a[i].d == -1){
				if (par[p].empty())
					par[p].push_back(i);
				else{
					int j = par[p].back();
					par[p].pop_back();
					ans[i] = ans[j] = (a[i].x - (a[j].d == 1 ? a[j].x : -a[j].x)) / 2;
				}
			}
			else{
				par[p].push_back(i);
			}
		}
		forn(p, 2){
			while (int(par[p].size()) > 1){
				int i = par[p].back();
				par[p].pop_back();
				int j = par[p].back();
				par[p].pop_back();
				ans[i] = ans[j] = (2 * m - a[i].x - (a[j].d == 1 ? a[j].x : -a[j].x)) / 2;
			}
		}
		forn(i, n){
			printf("%d ", ans[i]);
		}
		puts("");
	}
	return 0;
}

#include <bits/stdc++.h>     

using namespace std;

const int INF = int(1e9);

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++)
		cin >> a[i];
	vector<int> pos;
	for(int i = 0; i < n; i++)
		if(a[i] == 1)
			pos.push_back(i);
	int k = pos.size();
	vector<vector<int>> dp(n + 1, vector<int>(k + 1, INF));
	dp[0][0] = 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j <= k; j++)
		{
		 	if(dp[i][j] == INF) continue;
		 	dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
		 	if(j < k && a[i] == 0)
		 		dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(pos[j] - i));
		}
	cout << dp[n][k] << endl;
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<int, int> pt;

const int MOD = 998244353;

int norm(int a) {
	while (a >= MOD)
		a -= MOD;
	while (a < 0)
		a += MOD;
	return a;
}
int mul(int a, int b) {
	return int(a * 1ll * b % MOD);
}
int binPow(int a, int k) {
	int ans = 1;
	while (k > 0) {
		if (k & 1)
			ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}
int inv(int a) {
	return binPow(a, MOD - 2);
}

vector< vector<int> > d;
int n, m;

inline bool read() {
	if(!(cin >> n >> m))
		return false;
	d.resize(n, vector<int>(m));
	fore (i, 0, n) fore (j, 0, m)
		cin >> d[i][j];
	return true;
}

inline void solve() {
	int invFact = 1;
	fore (i, 1, n + 1)
		invFact = mul(invFact, i);
	invFact = inv(invFact);
	
	int E = 0;
	fore (j, 0, m) {
		vector<int> cnt(n + 1, 0);
		fore (i, 0, n)
			cnt[n + 1 - d[i][j]]++;
		
		vector<int> d(n + 1, 0);
		d[0] = 1;
		int rem = 0;
		fore (i, 0, n) {
			rem += cnt[i];
			d[i + 1] = norm(d[i + 1] + mul(d[i], rem));
			rem = max(0, rem - 1);
		}
//		cerr << d[n] << " - " << norm(1 - mul(d[n], invFact)) << endl;
		E = norm(E + 1 - mul(d[n], invFact));
	}
	cout << E << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>     

using namespace std;

const int N = 543;
const long long INF = (long long)(1e18);

struct Matching
{
 	int n1, n2;
 	vector<set<int>> g;
 	vector<int> mt, used;

 	void init()
 	{
 	 	mt = vector<int>(n2, -1);
 	}

 	int kuhn(int x)
 	{
 	 	if(used[x] == 1) return 0;
 	 	used[x] = 1;
 	 	for(auto y : g[x])
 	 		if(mt[y] == -1 || kuhn(mt[y]) == 1)
 	 		{
 	 		 	mt[y] = x;
 	 		 	return 1;
 	 		}
 	 	return 0;
 	}

 	int calc()
 	{
 	 	init();
 	 	int sum = 0;
 	 	for(int i = 0; i < n1; i++)
 	 	{
 	 		used = vector<int>(n1, 0);
 	 		sum += kuhn(i);
 	 	}
 	 	return sum;
 	}

 	void remove_vertex(int v, bool right)
 	{
 	 	if(right)
 	 	{
 	 		for(int i = 0; i < n1; i++)
 	 			g[i].erase(v);
 	 	}
 	 	else
 	 		g[v].clear();
 	}

 	void add_edge(int x, int y)
 	{
 		g[x].insert(y);
 	}

 	Matching() {};
 	Matching(int n1, int n2) : n1(n1), n2(n2)
 	{
 		g.resize(n1);
 	};
};

int n, m, k;
long long dp[N][N];
int p[N][N];
vector<int> g[N];
long long x[N], y[N];

int main()
{
	cin >> n >> m >> k;
	for(int i = 0; i < m; i++)
	{
	 	int u, v;
	 	cin >> u >> v;
	 	--u;
	 	--v;
	 	g[u].push_back(v);
	}
	for(int i = 0; i < k; i++)
		cin >> x[i] >> y[i];

	Matching mt(n, n);
	for(int i = 0; i < n; i++)
		for(auto j : g[i])
			mt.add_edge(i, j);
	int cnt = mt.calc();
	int cur = cnt;
	vector<int> seq;
	while(cur > 0)
	{
		int idx = 0;
		for(int i = 0; i < n; i++)
		{
		 	Matching mt2 = mt;
		 	mt2.remove_vertex(i, false);
		 	if(mt2.calc() < cur)
		 		idx = i + 1;
		 	mt2 = mt;
		 	mt2.remove_vertex(i, true);
		 	if(mt2.calc() < cur)
		 		idx = -(i + 1);
		}
		assert(idx != 0);
		seq.push_back(idx);
		mt.remove_vertex(abs(idx) - 1, idx < 0);
		cur--;
	}	
	reverse(seq.begin(), seq.end());
	for(int i = 0; i <= k; i++)
		for(int j = 0; j <= cnt; j++)
			dp[i][j] = -INF;
	dp[0][cnt] = 0;
	for(int i = 0; i < k; i++)
		for(int j = 0; j <= cnt; j++)
		{
			if(dp[i][j] == -INF) continue;
			for(int z = 0; z <= j; z++)
			{
				if(i + 1 + z >= n) continue;
			 	int t = j - z;
			 	long long add = max(0ll, x[i] - t * y[i]);
			 	if(dp[i + 1][z] < dp[i][j] + add)
			 	{
			 	 	dp[i + 1][z] = dp[i][j] + add;
			 	 	p[i + 1][z] = j;
			 	}
			}
		}
	cur = max_element(dp[k], dp[k] + cnt + 1) - dp[k];
	vector<int> res;
	for(int i = k; i > 0; i--)
	{
		res.push_back(0);
		for(int j = p[i][cur] - 1; j >= cur; j--)
			res.push_back(seq[j]);
		cur = p[i][cur];	
	}
	reverse(res.begin(), res.end());
	cout << res.size() << endl;
	for(auto x : res) cout << x << " ";
	cout << endl;
}

Consider the minimum possible answer. Since you have to do all $$$s$$$ problems in $$$n$$$ days, you can do $$$\lfloor \frac s n \rfloor$$$ in some of them and then $$$\lceil \frac s n \rceil$$$ in the rest of the days. Thus, $$$\lceil \frac s n \rceil$$$ is the minimum possible $$$a_n$$$.

Now it would be great if the function that tells if some $$$x$$$ can be the number of problems during the last day was monotonous for all $$$x$$$ from $$$\lceil \frac s n \rceil$$$ to $$$\infty$$$. So that function first returns true for some prefix of values, then it returns false. Intuitively, it sounds monotonous: the smaller values allow a lot of freedom for the construction and the larger values fail because they require too many problems in total.

The difficulty rises from the fact we not only have to prove that, but we also have to find a way to ask the result of that function quickly.

If we didn't have to, the proof would not be too hard.

Now that we are absolutely sure that the function is monotonous, let's change our approach.

Obviously, we should try binary search on $$$x$$$. So we have the total number of problems $$$s$$$, the number of days $$$n$$$ and some fixed number of problems during the last day $$$x$$$.

Our second educated guess can be of the following kind. Given fixed $$$n$$$ and $$$x$$$, all the possible values of $$$s$$$ that can correspond to some construction are some segment of integers. That can actually be proven in the similar manner.

So we can binary search for a solution for $$$x$$$ from $$$\lceil \frac s n \rceil$$$ to $$$s$$$. $$$f(x)$$$ can be the smallest total number of problems such that there exists a distribution. Since that value is monotonous, you can look for the largest $$$x$$$ such that $$$f(x) \le s$$$.

To calculate the function you can observe that the sequence $$$x$$$, $$$\lceil \frac x 2 \rceil$$$, $$$\left\lceil \frac{\lceil \frac x 2 \rceil}{2} \right\rceil$$$, $$$\dots$$$ has only ones after $$$\log(x)$$$ values.

Overall complexity: $$$O(\log^2 s)$$$ per testcase.

fun main() {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val a = readLine()!!.split(" ").map { it.toLong() }
        val answer = a.sortedDescending().withIndex().maxOf { (it.index + 1) * it.value }
        println(answer)
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val s = readLine()!!
        val answer = s.count { it == 'w' } + s.split("w").sumOf { it.length / 2 }
        println(answer)
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k) = readLine()!!.split(" ").map { it.toInt() }
        val p = readLine()!!.split(" ").map { it.toInt() }
        val answer = (1..n / k).maxOf { d ->
            val m = d * k
            p.subList(n - m, n - m + d).sum()
        }
        println(answer)
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val a = readLine()!!.split(" ").map { it.toInt() }
            .withIndex().sortedBy { it.value }
        var i = 0
        var j = n - 1
        val answer = ArrayList<Int>(n)
        var bc = 0
        while (i <= j) {
            if (bc >= a[i].value) {
                answer += a[i++].index
                bc = 1
            } else {
                answer += a[j--].index
                bc++
            }
        }
        println(answer.joinToString(" ") { (it + 1).toString() })
    }
}

fun main() = repeat(readLine()!!.toInt()) {
	val n = readLine()!!.toInt()
	val a = readLine()!!.split(" ").map { it.toInt() }
	val b = readLine()!!.split(" ").map { it.toInt() }
	
	var ans = -1
	var ans_shift = -1
	for (shift in 0 until n) {
		var res = 1e9.toInt()
		for(i in 0 until n)
			res = Math.min(res, Math.abs(a[i] - b[(i + shift) % n]))
		if (res > ans) {
			ans = res
			ans_shift = shift
		}
	}	

	println(IntArray(n) { (it + ans_shift) % n + 1 }.joinToString(" ")) 
}

import java.util.*

fun main() {
    val (n, k, x) = readLine()!!.split(" ").map { it.toInt() }
    val a = readLine()!!.split(" ").map { it.toInt() }
    var l = 0L
    var r = 10L * 1000 * 1000 * 1000
    var res = -1L

    fun can(sum : Long) : Boolean {
        var cursum = 0L
        var need = 0
        var cur = PriorityQueue<Int>(compareBy<Int> { -it })
        for (i in 0 until n) {
            cursum += a[i]
            cur.add(a[i])
            while (cur.size > x || cursum > sum) {
                cursum -= cur.first()
                cur.remove()
                need += 1
            }
            if (cur.size == x) {
                cursum = 0L
                cur.clear()
            }
        }
        return need <= k
    }

    while (l <= r) {
        val mid = (l + r) / 2
        if (can(mid)) {
            res = mid
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    println(res)
}

fun main() {
	val (n, k) = readLine()!!.split(' ').map { it.toInt() }
	val a =	readLine()!!.split(" ").map { it.toInt() }.sorted()
	
	val p = IntArray(n + 1) { 0 }
	for (i in 0 until n) p[i + 1] = p[i] + a[i]
	
	val dp = Array(n + 1) { IntArray(k + 1) { -1 } }

 	dp[0][0] = 0
 	for (i in 0 until n) {
 		for (j in 0 until k + 1) {
 			if (dp[i][j] < 0)
 				continue
 			dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j])
 			val maxx = Math.min(k - j, (n - i) / 2)
 			for (x in 1..maxx)
 				dp[i + 2 * x][j + x] = Math.max(dp[i + 2 * x][j + x], dp[i][j] + p[i + 2 * x] - p[i + x] - p[i + x] + p[i])	
 		}
 	}
 	
 	println(dp[n][k])
}

fun main() {
	val (n, m, k) = readLine()!!.split(" ").map { it.toInt() }	
	val a = readLine()!!.split(" ").map { it.toLong() }
	val b = readLine()!!.split(" ").map { it.toLong() }
	val c = Array(n) { readLine()!!.split(" ").map { it.toLong() } }
	
	val ev = Array(n + m) {
		if (it < n)
			longArrayOf(a[it], 1L, it.toLong())
		else
			longArrayOf(b[it - n], 0L, (it - n).toLong())
	}
	
	ev.sortWith(compareBy({ it[0] }))
	
	val vals = LongArray(n + m) { 0 }
	
	for (e in 0 until n + m) {
		if (ev[e][1] == 1L) {
			val i = ev[e][2].toInt()
			vals[e] = b.indices.filter { b[it] <= ev[e][0] }.map { c[i][it] }.max()!!
		} else {
			val j = ev[e][2].toInt()
			vals[e] = a.indices.filter { a[it] <= ev[e][0] }.map { c[it][j] }.max()!!
		}
	}
	
	var ans = 1e18.toLong()
	
	for (bonus in 1 until n + m) {
		vals[bonus] += k.toLong()
		var (res, cur, mx) = LongArray(3) { 0 }
		var i = 0
		while (true) {
			while (i < n + m && ev[i][0] <= cur) {
				mx = Math.max(mx, vals[i])
				++i;
			}
			if (i == n + m) break
			val need = (ev[i][0] - cur + mx - 1) / mx
			res += need
			cur += need * mx
		}
		ans = Math.min(ans, res)
		vals[bonus] -= k.toLong()
	}

	println(ans)
}

import java.io.PrintWriter

fun main() {
	val (n, m, q) = readLine()!!.split(' ').map { it.toInt() }
	val s = Array(n) { readLine()!! }
	val c = Array(m + 1) { IntArray(n) { 0 } }
	val rc = Array(m + 1) { IntArray(n) { 0 } }
	
	for (j in m - 1 downTo 0) {
		val cur = Array(n) { intArrayOf(s[it][j].toInt(), c[j + 1][it], it) }
		cur.sortWith(compareBy({it[0]}, {it[1]}))
		for (i in 0 until n) rc[j][i] = cur[i][2]
		c[j][cur[0][2]] = 0
		for (i in 1 until n) {
			val add = if (cur[i][0] == cur[i - 1][0] && cur[i][1] == cur[i - 1][1]) 0 else 1
			c[j][cur[i][2]] = c[j][cur[i - 1][2]] + add
		}
	}
	
	val writer = PrintWriter(System.out)
	
	repeat(q) {
		val t = readLine()!!
		var ans = 0
		var j = 0
		while (j < m) {
			var (nj, L, R) = intArrayOf(j, 0, n - 1)
			while (nj < m) {
				var (l1, r1, nL) = intArrayOf(L, R, R + 1)
				while (l1 <= r1) {
					val mid = (l1 + r1) / 2
					if (s[rc[j][mid]][nj] >= t[nj]) {
						nL = mid
						r1 = mid - 1
					} else {
						l1 = mid + 1
					}
				}
				
				var (l2, r2, nR) = intArrayOf(nL, R, nL - 1)
				while (l2 <= r2) {
					val mid = (l2 + r2) / 2
					if (s[rc[j][mid]][nj] <= t[nj]) {
						nR = mid
						l2 = mid + 1
					} else {
						r2 = mid - 1
					}
				}
				
				if (nL > nR)
					break
					
				L = nL
				R = nR
				++nj
			}
			
			if (j == nj) {
				ans = 0
				break
			}
			
			ans += 1
			j = nj
		}
		
		writer.println(ans - 1)
	}
	
	writer.close()
}

fun main() {
	val MOD = 998244353
	
	fun add(x : Int, y : Int) : Int {
		return x + y - if (x + y < MOD) 0 else MOD	
	}
	
	fun mul(x : Int, y : Int) : Int {
		return (1L * x * y % MOD).toInt()
	}
	
	val inv = IntArray(60) { 0 }.also { it[0] = 1; it[1] = (MOD + 1) / 2 }
	for (i in 2 until 60) {
		inv[i] = mul(inv[i - 1], inv[1])
	}
	
	val n = readLine()!!.toInt()
	val a =	readLine()!!.split(" ").map { it.toLong() }
	val target = a.fold(0.toLong()) { res, it -> res xor it }
	val dp = Array(n) { Array(2) { IntArray(2) { 0 } } }
	
	var ans = 0
	
	val m = 1 shl (n - 1)
	for (mask in 0 until m) {
		val cur = Array(n - 1) { longArrayOf(a[it], a[it + 1]) }
		val used = BooleanArray(n - 1) { false }
		
		for (pw in 59 downTo 0) {
			for (i in 0 until n)
				for (cnt in 0 until 2)
					for (fl in 0 until 2)
						dp[i][cnt][fl] = 0
			dp[0][0][0] = 1
			for (i in 0 until n - 1) {
				for (cnt in 0 until 2) {
					for (fl in 0 until 2) {
						if (dp[i][cnt][fl] == 0)
							continue
						val (l, r) = cur[i]
						if ((l shr pw) == (r shr pw)) {
							if (!used[i] && ((mask shr i) and 1) == 1)
								continue
							val c = (l shr pw).toInt()
							val len = (cur[i][1] - cur[i][0] + 1)
							dp[i + 1][cnt xor c][fl] = add(dp[i + 1][cnt xor c][fl], mul((len % MOD).toInt(), dp[i][cnt][fl]))
						} else for (c in 0 until 2) {
							if (!used[i] && (c != (mask shr i) and 1))
								continue
							val nl = if (c == 1) 0L else l
							var nr = if (c == 1) r - (1L shl pw) else (1L shl pw) - 1
							val len = nr - nl + 1
							val nfl = if (len == (1L shl pw) && (c != ((mask shr i) and 1))) 1 else 0
							dp[i + 1][cnt xor c][fl or nfl] = add(dp[i + 1][cnt xor c][fl or nfl], mul((len % MOD).toInt(), dp[i][cnt][fl]))
						}
					}
				}
			}
			
			var cnt = ((target shr pw) and 1).toInt()
			ans = add(ans, mul(dp[n - 1][cnt][1], inv[pw]))
			if (pw == 0) 
				ans = add(ans, dp[n - 1][cnt][0])
			
			for (i in 0 until n - 1) {
				val (l, r) = cur[i]
				if ((l shr pw) == (r shr pw)) {
					val c = (l shr pw)
					cnt = cnt xor c.toInt()
					cur[i][0] -= c shl pw
					cur[i][1] -= c shl pw
				} else {
					used[i] = true
					val c = (mask shr i) and 1
					cnt = cnt xor c.toInt()
					cur[i][0] = if (c == 1) 0 else cur[i][0]
					cur[i][1] = if (c == 1) cur[i][1] - (1L shl pw) else (1L shl pw) - 1
				}
			}
			
			if (cnt != 0)
				break
		}
	}
	
	println(ans)
}

#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <cmath>

#define forn(i, n) for(int i=0;i<n;++i)
#define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define x first
#define y1 ________y1
#define y second
#define ft first
#define sc second
#define pt pair<int, int>

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;

using namespace std;

const int INF = 1000 * 1000 * 1000;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

li n;

inline void read() {	
	cin >> n;
}

inline void solve() {
	if (n == 1 || n == 2 || n == 4) {
		cout << -1 << endl;
		return;
	}
	if (n % 3 == 0) {
		cout << n / 3 << ' ' << 0 << ' ' << 0 << endl;
	} else if (n % 3 == 1) {
		cout << (n - 7) / 3 << ' ' << 0 << ' ' << 1 << endl;
	} else {
		cout << (n - 5) / 3 << ' ' << 1 << ' ' << 0 << endl;
	}
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    cerr << setprecision(10) << fixed;
    
    int t; cin >> t;
    while(t--) {
    	read();
    	solve();
    }
 
    //cerr << "TIME: " << clock() << endl;
}

#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <cmath>

#define forn(i, n) for(int i=0;i<n;++i)
#define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define x first
#define y1 ________y1
#define y second
#define ft first
#define sc second
#define pt pair<int, int>

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;

using namespace std;

const int INF = 1000 * 1000 * 1000;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);
const int N = 200 * 1000 + 13;

int n, k;
int a[N];

inline void read() {	
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> a[i];
}

inline void solve() {
	sort(a, a + n);
	reverse(a, a + n);
	li ans = 0;
	for (int i = 0; i <= k; i++) {
		ans += a[i];
	}
	cout << ans << endl;
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    cerr << setprecision(10) << fixed;
    
    int t; cin >> t;
    while(t--) {
    	read();
    	solve();
 	}
    //cerr << "TIME: " << clock() << endl;
}

#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <cmath>

#define forn(i, n) for(int i=0;i<n;++i)
#define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define x first
#define y1 ________y1
#define y second
#define ft first
#define sc second
#define pt pair<int, int>

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;

using namespace std;

const int INF = 1000 * 1000 * 1000;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

int n;

inline void read() {	
	cin >> n;
}

inline void solve() {
	multiset<int> was;
	for (int i = 1; i <= n; i++) {
		was.insert(i);
	}
	vector<pair<int, int> > ans;
	for (int i = 0; i < n - 1; i++) {
		auto it = was.end();
		it--;
		int a = *it;
		was.erase(it);
		it = was.end();
		it--;
		int b = *it;
		was.erase(it);
		was.insert((a + b + 1) / 2);
		ans.pb(mp(a, b));
	}
	cout << *was.begin() << endl;
	for (int i = 0; i < sz(ans); i++) {
		cout << ans[i].ft << ' ' << ans[i].sc << endl;
	}	
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    cerr << setprecision(10) << fixed;
    
    int t; cin >> t;
    while(t--) {
    	read();
    	solve();
    }
    //cerr << "TIME: " << clock() << endl;
}

#include<bits/stdc++.h>

using namespace std;

char buf[200043];

int main()
{
	int t;
	scanf("%d", &t);
	for(int tc = 1; tc <= t; tc++) {
		int n;
		scanf("%d", &n);
		scanf("%s", buf);
		string s = buf;
		queue<int> q;
		int cur = 0;
		for(int i = 0; i < n; i++)
		{
		 	if(i > 0 && s[i] != s[i - 1])
		 		cur++;
		 	if(i > 0 && s[i] == s[i - 1])
		 		q.push(cur);
		}
		int deleted = 0;       
		int score = 0;
		for(int i = 0; i < n; i++)
		{
			if(q.empty())
				break;
			q.pop();
			deleted++;
			score++;
			while(!q.empty() && q.front() == i)
			{
				q.pop();
				deleted++; 	
			}
			deleted++;
			//cerr << deleted << endl;
		}
		score += (n - deleted + 1) / 2;
		printf("%d\n", score);
	}
}

#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <cmath>

#define forn(i, n) for(int i=0;i<n;++i)
#define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define x first
#define y1 ________y1
#define y second
#define ft first
#define sc second
#define pt pair<int, int>

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;

using namespace std;

const int INF = 1000 * 1000 * 1000;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);
const int N = 200 * 1000 + 13;

int n;
string s;
string revS;
vector<int> posS[30];
vector<int> posT[30];
int cnt[30];
int t[N];

inline int sum (int r) {
	int result = 0;
	for (; r >= 0; r = (r & (r+1)) - 1)
		result += t[r];
	return result;
}

inline void inc (int i, int d) {
	for (; i < n; i = (i | (i+1)))
		t[i] += d;
}

int sum (int l, int r) {
	return sum (r) - sum (l-1);
}
     
inline void read() {	
	cin >> n >> s;
}

inline void solve() {
	revS = s;
	reverse(all(revS));
	for (int i = 0; i < sz(s); i++) {
		posS[s[i] - 'a'].pb(i);
		posT[revS[i] - 'a'].pb(i);
	}
	li ans = 0;
	for (int i = 0; i < sz(revS); i++) {
		int let = revS[i] - 'a';
		int cur = posS[let][cnt[let]];
		int oldC = cur;
		cur += sum(cur, n - 1);
		int need = i;
		ans += cur - need;
		inc(oldC, 1);
		cnt[let]++;
	}
	cout << ans << endl;
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    srand(time(NULL));
    cerr << setprecision(10) << fixed;
    
    read();
    solve();
 
    //cerr << "TIME: " << clock() << endl;
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;

int n, k;
vector<int> l, r, a;

inline bool read() {
	if(!(cin >> n >> k))
		return false;
	l.resize(n);
	r.resize(n);
	a.resize(n);
	
	fore(i, 0, n)
		cin >> l[i] >> r[i] >> a[i];
	
	return true;
}

inline void solve() {
	vector<li> d(n + 1, INF64);
	d[0] = 0;
	
	li ans = INF64;
	fore(i, 0, n) {
		li rem = k, total = d[i];
		for (int j = i; j < n; j++) {
			li cntReloads = (max(0LL, a[j] - rem) + k - 1) / k;
			if (cntReloads > r[j] - l[j])
				break;
			
			li newRem = (rem + cntReloads * k) - a[j];
			total += a[j];
			if (j + 1 < n) {
				if (l[j] + cntReloads < l[j + 1])
					d[j + 1] = min(d[j + 1], total + newRem);
			} else
				ans = min(ans, total);
			rem = newRem;
		}
	}
	if (ans > INF64 / 2)
		ans = -1;
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

typedef long long li;

const int N = 18;
const int M = (1 << N);
const li INF64 = li(1e18);

int n, m;
vector<int> g[N];
li sum[N];
int need_mask[N];
li dp[N + 1][N + 1][M];
bool p[N + 1][N + 1][M];

vector<int> order;       
vector<int> used;

void dfs(int x, bool build_topo)
{
    if(used[x])
    	return;
    used[x] = 1;
    for(auto y : g[x])
    	dfs(y, build_topo);
    if(build_topo)
    	order.push_back(x);
}

int main()
{
	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
	 	int x, y, w;
	 	cin >> x >> y >> w;
	 	--x;
	 	--y;
	 	sum[x] += w;
	 	sum[y] -= w;
	 	g[x].push_back(y);
	}
	used.resize(n);
	for(int i = 0; i < n; i++)
		dfs(i, true);
	for(int i = 0; i < n; i++)
	{
	 	used = vector<int>(n, 0);
	 	dfs(i, false);
	 	for(int j = 0; j < n; j++)
	 		if(j != i && used[j] == 1)
	 			need_mask[i] |= (1 << j);		
	}
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= n; j++)
			for(int k = 0; k < (1 << n); k++)
				dp[i][j][k] = INF64;
	dp[0][0][0] = 0;
	reverse(order.begin(), order.end());
	for(int i = 0; i < n; i++)
		for(int j = 0; j <= n; j++)
			for(int k = 0; k < (1 << n); k++)
			{
			 	if(dp[i][j][k] > INF64 / 2)
			 		continue;
			 	if(j == n)
			 	{
			 	 	if(dp[i + 1][0][k] > dp[i][j][k])
			 	 	{
			 	 	 	dp[i + 1][0][k] = dp[i][j][k];
			 	 	 	p[i + 1][0][k] = false;
			 	 	}
			 	}
			 	else
			 	{
			 		int v = order[j];
			 		li add = sum[v] * i;
			 		if(dp[i][j + 1][k] > dp[i][j][k])
			 		{
			 		 	dp[i][j + 1][k] = dp[i][j][k];
			 		 	p[i][j + 1][k] = false;
			 		}
			 		if(((k & (1 << v)) == 0) && ((need_mask[v] & k) == need_mask[v]))
			 		{
			 		 	int nk = k | (1 << v);
			 		 	if(dp[i][j + 1][nk] > dp[i][j][k] + add)
			 		 	{
			 		 	 	dp[i][j + 1][nk] = dp[i][j][k] + add;
			 		 	 	p[i][j + 1][nk] = true;
			 		 	}
				 	}
				}
			}
	vector<int> ans(n);
	int i = n;
	int j = 0;
	int k = (1 << n) - 1;
	while(i > 0 || j > 0 || k > 0)
	{
	 	if(j == 0)
	 	{
	 	 	j = n;
	 	 	i--;
	 	}
	 	else
	 	{
	 	 	if(p[i][j][k])
	 	 	{
	 	 	 	int v = order[j - 1];
	 	 	 	ans[v] = i;
	 	 	 	k ^= (1 << v);
	 		}
	 		j--;
	 	}
	}
	for(int i = 0; i < n; i++)
		cout << ans[i] << " \n"[i == n - 1];
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k) = readLine()!!.split(" ").map { it.toInt() }
        val n1 = n / (1 + k + k * k + k * k * k)
        val n2 = n1 * k
        val n3 = n2 * k
        val n4 = n3 * k
        println("$n1 $n2 $n3 $n4")
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k1, k2) = readLine()!!.split(" ").map { it.toInt() }
        val s = readLine()!!
        var m = 0
        var prev = 0
        for (c in s) {
            if (c == '1') {
                prev = minOf(k2 - prev, k1)
                m += prev
            } else {
                prev = 0
            }
        }
        println(m)
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k, x, y) = readLine()!!.split(" ").map { it.toInt() }
        val a = readLine()!!.split(" ").map { it.toInt() }.sorted()
        val maxSum = k * n.toLong()
        var sum = 0L
        var ans = 0
        var ok = true
        var i = 0
        while (i < n && sum + a[i] <= maxSum) {
            sum += a[i]
            if (ok && a[i] > k) {
                ok = false
                ans = (n - i) * x // can simply drop the rest 
            }
            i++
        }
        ans = if (ok) (n - i) * x // drop the rest
            else minOf(ans, (n - i) * x + y) // drop the rest & rearrange
        println(ans)
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, m) = readLine()!!.split(" ").map { it.toInt() }
        val e = List(m) {
            val (u, v, w) = readLine()!!.split(" ").map { it.toInt() }
            Tun(u - 1, v - 1, w)
        }
        val a = solveDungeon(n, e)
        if (a != null) {
            println("YES")
            println(a.joinToString(" "))
        } else {
            println("NO")
        }
    }
}

private class Tun(val u: Int, val v: Int, val w: Int)

private fun solveDungeon(n: Int, e: List<Tun>): IntArray? {
    val a = IntArray(n)
    for (t in e.sortedByDescending { it.w }) {
        if (a[t.u] == 0) a[t.u] = t.w
        if (a[t.v] == 0) a[t.v] = t.w
        if (t.w != minOf(a[t.u], a[t.v])) return null
    }
    return a
}

fun main() {
    val (n, m, k) = readLine()!!.split(" ").map { it.toInt() }
    val inf = Int.MAX_VALUE - 1
    val s = IntArray(n) { inf }
    s[k - 1] = 0
    repeat(m) {
        val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1 }
        val sx = s[x]
        val sy = s[y]
        s[x] = minOf(sx + 1, sy)
        s[y] = minOf(sy + 1, sx)
    }
    println(s.joinToString(" ") { (if (it == inf) -1 else it).toString() })
}

import kotlin.math.*

fun main() {
    val (n, m, q) = readLine()!!.split(" ").map { it.toInt() }
    val a = Array(n) { readLine()!!.split(" ").map { it.toInt() }.toIntArray() }
    val rs = LongArray(n) { i -> (0 until m).map { j -> a[i][j].toLong() }.sum() }.toDistSum()
    val cs = LongArray(m) { j -> (0 until n).map { i -> a[i][j].toLong() }.sum() }.toDistSum()
    fun ans() = rs.min()!! + cs.min()!!
    print(ans())
    repeat(q) {
        val (x1, y1, z) = readLine()!!.split(" ").map { it.toInt() }
        val (x, y) = (x1 - 1) to (y1 - 1)
        val d = (z - a[x][y]).toLong()
        for (i in 0 until n) rs[i] += abs(x - i) * d
        for (j in 0 until m) cs[j] += abs(y - j) * d
        a[x][y] = z
        print(" ${ans()}")
    }
}

private fun LongArray.toDistSum(): LongArray {
    val s = LongArray(size)
    var su = 0L
    var wsu = 0L
    var sd = 0L
    var wsd = 0L
    for (i in 0 until size) {
        sd += get(i)
        wsd += (i + 1) * get(i)
    }
    for (i in 0 until size) {
        wsd -= sd
        sd -= get(i)
        s[i] = wsu + wsd
        su += get(i)
        wsu += su
    }
    return s
}

fun main() {
    val (k, n) = readLine()!!.split(" ").map { it.toInt() }
    val p = readLine()!!.split(" ").map { it.toInt() }
    val x = readLine()!!.split(" ").map { it.toInt() }
    val c = solveCams(n, p, x)
    if (c == null) {
        println("NO")
    } else {
        println("YES")
        println("$$${c.s1} $$${c.p1}")
        println("$$${c.s2} $$${c.p2}")
    }
}

private class Cams(val s1: Int, val p1: Int, val s2: Int, val p2: Int)

private tailrec fun gcd(x: Int, y: Int): Int = if (y == 0) x else gcd(y, x % y)

private fun solveCams(n: Int, p: List<Int>, x: List<Int>): Cams? {
    fun place2(s1: Int, p1: Int): Cams? {
        val f = BooleanArray(n) { j -> (x[j] - s1) % p1 == 0 }
        val i = f.indexOf(false)
        if (i < 0) return Cams(s1, p1, s1, p1)
        val s2 = x[i]
        var j = i + 1
        while (j < n && f[j]) j++
        if (j >= n) return Cams(s1, p1, s2, p[0])
        var p2m = x[j] - s2
        while (++j < n) {
            if (!f[j]) p2m = gcd(p2m, x[j] - s2)
        }
        for (p2 in p) if (p2m % p2 == 0) {
            return Cams(s1, p1, s2, p2)
        }
        return null
    }
    fun tryPlace2(s1: Int, p1m: Int): Cams? {
        for (p1 in p) if (p1m % p1 == 0) {
            place2(s1, p1)?.let { return it }
        }
        return null
    }
    if (n == 2) return Cams(x[0], p[0], x[1], p[0])
    for (t1 in 1..2) {
        tryPlace2(x[0], x[t1] - x[0])?.let { return it }
    }
    return tryPlace2(x[1], x[2] - x[1])
}

import java.lang.AssertionError
 
private fun readLn() = readLine()!! // string line
private fun readInt() = readLn().toInt() // single int
private fun readLong() = readLn().toLong() // single long
private fun readDouble() = readLn().toDouble() // single double
private fun readStrings() = readLn().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints
private fun readLongs() = readStrings().map { it.toLong() } // list of longs
private fun readDoubles() = readStrings().map { it.toDouble() } // list of doubles
 
private fun myAssert(x: Boolean) {
    if (!x) {
        throw AssertionError()
    }
}
 
fun main(args: Array<String>) {
    var (tt, n) = readInts()
    var lstart = IntArray(tt)
    var rstart = IntArray(tt)
    for (i in 0 until tt) {
        var (x, y) = readInts()
        lstart[i] = x
        rstart[i] = y
    }
    var l = ArrayList<Int>()
    var r = ArrayList<Int>()
    for (i in 0 until n) {
        var (x, y) = readInts()
        l.add(x)
        r.add(y)
    }
    var order = ArrayList<Int>()
    for (i in 0 until n) {
        order.add(i)
    }
    order.sortWith(compareBy({l[it] + r[it]}, {l[it]}))
    val inf = 787788789
    fun getDistance(L: Int, R: Int) : Int {
        var low = 0
        var high = n
        while (low < high) {
            var mid = (low + high) / 2
            if (l[order[mid]] + r[order[mid]] < L + R ||
                (l[order[mid]] + r[order[mid]] == L + R && l[order[mid]] < L)) {
                low = mid + 1
            } else {
                high = mid
            }
        }
        if (low < n && l[order[low]] + r[order[low]] == L + R) {
            return l[order[low]] - L
        }
        return inf
    }
    var res = IntArray(tt) {-1}
    for (qq in 0 until tt) {
        var L = lstart[qq]
        var R = rstart[qq]
        var a = getDistance(L, R - 2) + 1
        var b = getDistance(L, R)
        var c = getDistance(L + 2, R) + 1
        res[qq] = maxOf(minOf(a, b), minOf(b, c))
        if (res[qq] >= inf) {
            res[qq] = -1
        }
    }
    println(res.joinToString(" "))
}

import kotlin.math.abs

fun main() {
    val INF = 1e9.toInt()
    val INF64 = 1e18.toLong()
    val LOG = 60
    var (n, m, q, s) = readLine()!!.split(' ').map { it.toInt() }
    s--
    val a = readLine()!!.split(' ').map { it.toInt() }
    
    val summask = LongArray(1 shl n) { 0 }
    for (mask in 0 until (1 shl n)) {
        for (i in 0 until n) {
            if ((mask and (1 shl i)) > 0)
                summask[mask] += a[i].toLong()
        }
    }

    val d = Array(n) { IntArray(n) { INF } }
    for (i in 0 until m) {
        val (x, y) = readLine()!!.split(' ').map { it.toInt() }
        d[x - 1][y - 1] = 1
    }
    
    val C = readLine()!!.split(' ').map { it.toLong() }

    for (k in 0 until n) {
        for (i in 0 until n) {
            for (j in 0 until n)
                d[i][j] = minOf(d[i][j], d[i][k] + d[k][j])
        }
    }

    val dp = Array(n) { Array(n) { IntArray(1 shl n) { INF } } }
    for (st in 0 until n) {
        dp[st][st][1 shl st] = 0

        for (mask in 0 until (1 shl n)) {
            for (i in 0 until n) {
                if ((mask and (1 shl i)) == 0)
                    continue
                for (j in 0 until n) {
                    if ((mask and (1 shl j)) > 0)
                        continue
                    dp[st][j][mask or (1 shl j)] =
                            minOf(dp[st][j][mask or (1 shl j)], dp[st][i][mask] + d[i][j])
                }
            }
        }
    }

    val bst = Array(n) { LongArray(n * n) { 0 } }
    for (i in 0 until n) {
        for (mask in 0 until (1 shl n)) {
            if ((mask and (1 shl i)) > 0) {
                for (j in 0 until n) {
                    if (dp[i][j][mask] != INF)
                        bst[i][dp[i][j][mask]] = maxOf(bst[i][dp[i][j][mask]], summask[mask])
                }
            }
        }
    }

    val steps = Array(LOG) { Array(n) { LongArray(n) { INF64 } } }
    for (i in 0 until n) {
        for (j in 0 until n)
            steps[0][i][j] = dp[i][j][(1 shl n) - 1].toLong()
    }

    for (t in 1 until LOG) {
        for (i in 0 until n) {
            for (j in 0 until n) {
                for (k in 0 until n)
                    steps[t][i][j] = minOf(steps[t][i][j], steps[t - 1][i][k] + steps[t - 1][k][j])
            }
        }
    }

    for (qr in 0 until q) {
        val sum = summask[(1 shl n) - 1]
        val need = C[qr] / sum

        var cur = LongArray(n) { INF64 }
        cur[s] = 0

        for (t in 0 until LOG - 1) {
            if ((need and (1L shl t)) > 0) {
                val ncur = LongArray(n) { INF64 }
                for (i in 0 until n) {
                    for (j in 0 until n)
                        ncur[i] = minOf(ncur[i], steps[t][j][i] + cur[j])
                }
                cur = ncur
            }
        }

        var ans = INF64
        for(i in 0 until n) {
            val lft = C[qr] % sum
            for (j in 0 until n * n) {
            	if (bst[i][j] >= lft)
            		ans = minOf(ans, cur[i] + j);
            }
        }

        println(ans)
    }
}

#include <bits/stdc++.h>

using namespace std;

int a1, a2, k1, k2, n;

inline void read() {
	cin >> a1 >> a2 >> k1 >> k2 >> n;	
}

inline void solve() {
	if (k1 > k2) {
		swap(k1, k2);
		swap(a1, a2);
	}
	int minCnt = max(0, n &mdash; a1 * (k1 &mdash; 1) &mdash; a2 * (k2 &mdash; 1));
	int maxCnt = 0;
	if (n <= a1 * k1) {
		maxCnt = n / k1;
	} else {
		maxCnt = a1 + (n &mdash; a1 * k1) / k2;
    }    
    cout << minCnt << ' ' << maxCnt << endl;
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    srand(time(NULL));
    cerr << setprecision(10) << fixed;
    
    read();
    solve();
 
    //cerr << "TIME: " << clock() << endl;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200 * 1000 + 13;

int n;
int a[N];

inline void read() {	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
}

inline void solve() {
	int pos = -1;
	li ans0 = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] == 0) {
			pos = i;
		}
		if (pos != -1) {
			ans0 += pos + 1;
		}
	}	
	int cnt1 = 0, cnt2 = 0;
	int bal = 0;
	li ansP = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] == 0) {
			cnt1 = 0, cnt2 = 0, bal = 0;
			continue;
		}
		if (bal % 2 == 0) {	
			cnt1++;
		} else {
			cnt2++;
		}
		if (a[i] < 0) {
			bal++;
		}
		if (bal % 2 == 0) {
			ansP += cnt1;
		} else {
			ansP += cnt2;
		}
	}
	cout << n * 1ll * (n + 1) / 2 - ans0 - ansP << ' ' << ansP << endl;
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    srand(time(NULL));
    cerr << setprecision(10) << fixed;
    
    read();
    solve();
 
    //cerr << "TIME: " << clock() << endl;
}

#include<bits/stdc++.h>

using namespace std;

int n;
string s, t;

inline void read() {	
	cin >> n >> s >> t;
}

inline void solve() {
	vector<int> pos01, pos10;
	for (int i = 0; i < n; i++) {
		if (s[i] != t[i]) {
			if (s[i] == 'a') {
				pos01.pb(i);
			} else {
				pos10.pb(i);
			}
		}
	}
	if (sz(pos01) % 2 != sz(pos10) % 2) {
		cout << -1 << endl;
		return;
	}
	vector<pair<int, int> > ans;
	for (int i = 0; i + 1 < sz(pos01); i += 2) {
		ans.pb(mp(pos01[i], pos01[i + 1]));
	}
	for (int i = 0; i + 1 < sz(pos10); i += 2) {
		ans.pb(mp(pos10[i], pos10[i + 1]));
	}
	if (sz(pos01) % 2) {
		int x = pos01.back();
		int y = pos10.back();
		ans.pb(mp(x, x));
		ans.pb(mp(x, y));
	}
	cout << sz(ans) << endl;
	for (int i = 0; i < sz(ans); i++) {
		cout << ans[i].ft + 1 << ' ' << ans[i].sc + 1 << endl;
	}
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    srand(time(NULL));
    cerr << setprecision(10) << fixed;
    
    read();
    solve();
 
    //cerr << "TIME: " << clock() << endl;
}

#include <iostream>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int n;

int main() {
    cin >> n;
    long double sum1 = 0, sum2 = 0;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) {
        if (s[i] != '?') {
            if (i < n / 2) {
                sum1 += (long double)(s[i] - '0');
            } else {
                sum2 += (long double)(s[i] - '0');
            }
        } else {
            if (i < n / 2) {
                sum1 += (long double)4.5;
            } else {
                sum2 += (long double)4.5;   
            }
        }
    }
    if (fabsl(sum1 - sum2) < 1e-9) {
        cout << "Bicarp" << endl;
    } else {
        cout << "Monocarp" << endl;
    }
}

#include <iostream>
#include <set>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1000 * 1000 + 13;
const int M = 20 + 1;
const long long INF = 1000 * 1000 * 1000 * 1ll * 1000 * 1000 * 1000;

int n;
long long d[(1 << M)];
long long cnt[M][M];
vector<int> col[M];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        x--;
        col[x].push_back(i);
    }
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
            if (i == j) {
                continue;
            }
            if ((int)col[i].size() == 0 || (int)col[j].size() == 0) {
                continue;
            }
            int pos2 = 0;
            for (int pos1 = 0; pos1 < (int)col[i].size(); pos1++) {
                while (true) {
                    if (pos2 == (int)col[j].size() - 1 || col[j][pos2 + 1] > col[i][pos1]) {
                        break;
                    }
                    pos2++;
                }
                if (col[i][pos1] > col[j][pos2]) {
                    cnt[i][j] += pos2 + 1;
                }
            }
        }
    }

    for (int mask = 0; mask < (1 << 20); mask++) {
        d[mask] = INF;
    }
    d[0] = 0;
    for (int mask = 0; mask < (1 << 20); mask++) {
        vector<int> was;
        for (int i = 0; i < 20; i++) {
            if (mask & (1 << i)) {
                was.push_back(i);
            }
        }
        for (int i = 0; i < 20; i++) {
            if (mask & (1 << i)) {
                continue;
            }
            long long sum = 0;
            for (int j = 0; j < (int)was.size(); j++) {
                sum += cnt[was[j]][i];
            }
            int nmask = mask | (1 << i);
            d[nmask] = min(d[nmask], d[mask] + sum);
        }
    }
    cout << d[(1 << 20) - 1] << endl;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 1600043;

vector<int> g[N];
vector<int> gt[N];
int used[N];
vector<int> order;
int comp[N];
vector<int> result;
int v;

void add_edge(int v1, int v2)
{
	g[v1].push_back(v2);
	gt[v2].push_back(v1);
}

void add_disjunction(int v1, int v2)
{
	add_edge(v1 ^ 1, v2);
	add_edge(v2 ^ 1, v1);
}

void dfs1(int v)
{
	if(used[v]) return;
	used[v] = 1;
	for(auto u : g[v])
		dfs1(u);
	order.push_back(v);
}

void dfs2(int v, int cc)
{
	if(comp[v]) return;
	comp[v] = cc;
	for(auto u : gt[v])
		dfs2(u, cc);
}

bool solve2SAT()
{
	for(int i = 0; i < v * 2; i++)
		dfs1(i);
	reverse(order.begin(), order.end());
	int cc = 0;
	for(auto x : order)
	{
		if(comp[x] == 0)
		{
			cc++;
			dfs2(x, cc);
		}
	}
	for(int i = 0; i < v; i++)
	{
		if(comp[i * 2] == comp[i * 2 + 1])
			return false;
		else if(comp[i * 2] > comp[i * 2 + 1])
			result.push_back(i);
	}
	return true;
}

int main()
{
	int n, p, M, m;
	scanf("%d %d %d %d", &n, &p, &M, &m);
	v = p + M - 1;
	for(int i = 0; i < n; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		--x;
		--y;
		add_disjunction(x * 2, y * 2);
	}
	for(int i = 0; i < p; i++)
	{
		int l, r;
		scanf("%d %d", &l, &r);
		if(l != 1)
			add_disjunction((l - 2 + p) * 2, i * 2 + 1);
		if(r != M)
			add_disjunction((r - 1 + p) * 2 + 1, i * 2 + 1);
	}
	for(int i = 0; i < m; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		--x;
		--y;
		add_disjunction(x * 2 + 1, y * 2 + 1);
	}
	for(int i = 2; i <= M - 1; i++)
	{
	    int f1 = i - 2 + p;
	    int f2 = f1 + 1;
	    add_disjunction(f1 * 2, f2 * 2 + 1);
	}
	if(!solve2SAT())
	{
		puts("-1");
		return 0;
	}
	int k = 1;
	vector<int> stations;
	for(auto x : result)
		if(x < p)
			stations.push_back(x);
		else
			k = max(k, x - p + 2);
	printf("%d %d\n", int(stations.size()), k);
	for(auto x : stations)
		printf("%d ", x + 1);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

string s;

bool ok(string t){
    int msk = 0;
    
    for(int i = 0; i < int(t.size()); ++i){
	    if(isupper(t[i])) msk |= 1;
	    if(islower(t[i])) msk |= 2;
	    if(isdigit(t[i])) msk |= 4;
	}
	
	return msk == 7;
}

int main() {
	//freopen("input.txt", "r", stdin);
	int t;
	cin >> t;
	for(int i = 0; i < t; ++i){
    	cin >> s;
    	if(ok(s)){
    	    cout << s << endl;
    	    continue;
    	}
    	bool fnd = false;
        for(int i = 0; i < int(s.size()); ++i){
            string t = s;
            
            t[i] = '1';
            if(ok(t)){
    	        cout << t << endl;
    	        fnd = true;
    	        break;
    	    }
            t[i] = 'a';
            if(ok(t)){
    	        cout << t << endl;
    	        fnd = true;
    	        break;
    	    }
    	    t[i] = 'A';
            if(ok(t)){
    	        cout << t << endl;
    	        fnd = true;
    	        break;
    	    }
        }
    	
    	if(fnd) continue;
    	
    	if(isupper(s[2])){
    	    s[0] = 'a';
    	    s[1] = '1';
    	    cout << s << endl;
    	    continue;
    	}
    	if(islower(s[2])){
    	    s[0] = 'A';
    	    s[1] = '1';
    	    cout << s << endl;
    	    continue;
    	}
    	if(isdigit(s[2])){
    	    s[0] = 'a';
    	    s[1] = 'A';
    	    cout << s << endl;
    	    continue;
    	}
	}
	return  0;
}

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 

int main() {
	long long l, r;
	scanf("%lld%lld", &l, &r);
	puts("YES");
	forn(i, (r - l) / 2 + 1)
		printf("%lld %lld\n", l + i * 2, l + i * 2 + 1);
}

#include <bits/stdc++.h>

using namespace std;

const int N = 109;

int n;
int a[N];
map<int, int> m;
set <int> s[2];

int main() {
	int n;
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> a[i];
		m[a[i]]++;
	}

	int pos = 0;
	for(auto p : m)
		if(p.second == 1){
			s[pos].insert(p.first);
			pos = 1 - pos;
		}
		
	if(s[0].size() == s[1].size()){
		string res(n, 'A');
		for(int i = 0; i < n; ++i)
			if(s[1].count(a[i]))
				res[i] = 'B';
		
		cout << "YES" << endl;
		for(auto c : res) cout << c;
		cout << endl;
		return 0;
	}
	else{
		assert(int(s[0].size()) - 1 == int(s[1].size()));
		string res(n, 'A');
		for(int i = 0; i < n; ++i)
			if(s[1].count(a[i]))
				res[i] = 'B';
		
		int id = -1;
		for(auto p : m)
			if(p.second >= 3){
				id = p.first;
				break;
			}
			
		if(id == -1){
			cout << "NO" << endl;
			return 0;
		}
		
		bool flag = false;
		for(int i = 0; i < n; ++i){
			if(a[i] == id)
				if(!flag){
					flag = true;
					res[i] = 'B';
				}
		}
		
		cout << "YES" << endl;
		for(auto c : res) cout << c;
		cout << endl;
		return 0;
	}
	return 0;
}
                             	

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 

const int N = 1000 + 7;
const int MOD = 998244353;

int dp[N][2 * N][4];

int add(int a, int b){
	return (a + b) % MOD;
}

bool full(int mask){
	return (mask == 0 || mask == 3);
}

int get(int mask, int nmask){
	int cnt = __builtin_popcount(mask ^ nmask);
	if (cnt == 0) return 0;
	if (cnt == 2) return (full(mask) ? 1 : 2);
	return (full(mask) ? 0 : 1);
}

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	forn(i, 4)
		dp[1][0][i] = 1;
	
	for (int i = 1; i < n; ++i){
		forn(j, k + 1){
			forn(mask, 4){
				forn(nmask, 4){
					dp[i + 1][j + get(mask, nmask)][nmask] = add(dp[i + 1][j + get(mask, nmask)][nmask], dp[i][j][mask]);
				}
			}
		}
	}
	
	int ans = 0;
	forn(mask, 4){
		int nw = get(mask, mask ^ 3);
		if (k >= nw)
			ans = add(ans, dp[n][k - nw][mask]);
	}
	
	printf("%d\n", ans);
}        	

#include<bits/stdc++.h>

using namespace std;

#define sz(a) (int)(a.size())

const int N = int(1e6) + 9;
const int MOD = 998244353;

int n;
string s, l, r;
int dp[N];
int sumDP[N];

int sum(int a, int b){
	a += b;
	if(a >= MOD) a -= MOD;
	return a;
}

vector <int> z_function(string s){
	int n = sz(s);
	vector <int> z(n);
	for(int i = 1, l = 0, r = 0; i < n; ++i){
		if(i <= r)
			z[i] = min(r - i + 1, z[i - l]);
		while(i + z[i] < n && s[z[i]] == s[i + z[i]])
			++z[i];
		if(i + z[i] - 1 > r)
			l = i,  r = i + z[i] - 1;
	}
	return z;
}

//s[pos..] ? t
char cmp(vector <int> &zf, string &t, int pos){
	int len = sz(t);
	assert(pos + len + 1 < sz(zf));
	if(sz(s) - pos < len) return '<';
	
	int x = zf[len + 1 + pos];
	assert(x <= len);
	if(x == len) return '=';
	assert(pos + x < sz(s));
	assert(s[pos + x] != t[x]);
	if(s[pos + x] < t[x]) return '<';
	return '>';
}

int main() {
	//freopen("input.txt", "r", stdin);
	
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
	cin >> s >> l >> r;
	n = int(s.size());
	vector <int> zl = z_function(l + "#" + s);
	vector <int> zr = z_function(r + "#" + s);
	
	sumDP[n] = dp[n] = 1;
	for(int i = n - 1; i >= 0; --i){
		if(s[i] == '0'){
			if(l == "0") dp[i] = dp[i + 1];		
			else dp[i] = 0;
			sumDP[i] = sum(dp[i], sumDP[i + 1]);
			continue;
		}
		
		int L = sz(l) + i;
		char cl = cmp(zl, l, i);
		if(cl == '<') ++L;
		
		int R = sz(r) + i;
		char cr = cmp(zr, r, i);
		if(cr == '>') --R;

	 	int cur = 0;
	 	if(L <= R && L <= n){
	 		R = min(R, n);
	 		cur = sumDP[L];
	 		if(R != n) cur = sum(cur, MOD - sumDP[R + 1]);
	 	}
	 	dp[i] = cur;
	 	sumDP[i] = sum(dp[i], sumDP[i + 1]);
	}
	
	cout << dp[0] << endl;
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 300 * 1000 + 9;
const int LOGN = 19;
const int M = 21;
const long long INF64 = 1e18;

int n, m, q;
vector <pair<int, int> > g[N];
int p[LOGN][N];
int tin[N], tout[N], T;
long long h[N];
set <pair<int, int> > badEdges;
long long d[M + M][N];
bool u[N];

void dfs(int v, int pr){
	tin[v] = T++;
	p[0][v] = pr;
	u[v] = true;
	for(int i = 1; i < LOGN; ++i)
		p[i][v] = p[i - 1][ p[i - 1][v] ];
		
	for(auto e : g[v]){
		int to = e.first, len = e.second;
		if(!u[to]){
			h[to] = h[v] + len;
			dfs(to, v);
			
			if(v < to)
				badEdges.erase(make_pair(v, to));
			else
				badEdges.erase(make_pair(to, v));			
		}
	}	
		
	tout[v] = T;
}

bool isAncestor(int a, int b){
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int getLCA(int a, int b){
	if(isAncestor(a, b)) return a;
	if(isAncestor(b, a)) return b;
	
	for(int i = LOGN - 1; i >= 0; --i)
		if(!isAncestor(p[i][a], b))
			a = p[i][a];
	
	return p[0][a];
}

void dij(int st, long long d[N]){
	set<pair<long long, int> > q;
	for(int i = 0; i < n; ++i) d[i] = INF64;
	d[st] = 0;
	q.insert(make_pair(d[st], st));
	
	while(!q.empty()){
		int v = q.begin()->second;
		q.erase(q.begin());
		
		for(auto e : g[v]){
			int to = e.first, len = e.second;
			if(d[to] > d[v] + len){
				q.erase(make_pair(d[to], to));
				d[to] = d[v] + len;
				q.insert(make_pair(d[to], to));
			}
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	
	scanf("%d %d", &n, &m);
    for(int i = 0; i < m; ++i){
    	int u, v, w;
    	scanf("%d %d %d", &u, &v, &w);
    	--u, --v;
    	g[u].push_back(make_pair(v, w));
       	g[v].push_back(make_pair(u, w));
    }
	
    for(int v = 0; v < n; ++v)
    	for(auto e : g[v])
    		if(v < e.first)
    			badEdges.insert(make_pair(v, e.first));

    dfs(0, 0);

    int cpos = 0;
    for(auto e : badEdges)
    	dij(e.first, d[cpos++]);
    scanf("%d", &q);
    for(int tc = 0; tc < q; ++tc){
    	int u, v;
    	scanf("%d %d", &u, &v);
    	--u, --v;
    	int lca = getLCA(u, v);
    	long long ans = h[u] + h[v] - 2 * h[lca];
    	for(int i = 0; i < badEdges.size(); ++i)
    		ans = min(ans, d[i][u] + d[i][v]);
    		
    	printf("%lld\n", ans);
    }	
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef long long li;

mt19937 rnd(time(NULL));

struct node
{
	int x;
	int y;
	li sum;
	int siz;
	node* l;
	node* r;
	node() {};
	node(int x, int y, li sum, int siz, node* l, node* r) : x(x), y(y), sum(sum), siz(siz), l(l), r(r) {};
};

typedef node* treap;
typedef pair<treap, treap> ptt;

int getSiz(treap t)
{
	return (t ? t->siz : 0);
}

li getSum(treap t)
{
	return (t ? t->sum : 0);
}

treap fix(treap t)
{
	if(!t) return t;
	t->sum = getSum(t->l) + t->x + getSum(t->r);
	t->siz = getSiz(t->l) + 1 + getSiz(t->r);
	return t;
}

ptt split(treap t, int l)
{
	t = fix(t);
	if(!t) return make_pair(t, t);
	if(t->x < l)
	{
		auto z = split(t->r, l);
		t->r = z.x;
		return make_pair(fix(t), z.y);
	}
	else
	{
		auto z = split(t->l, l);
		t->l = z.y;
		return make_pair(z.x, fix(t));
	}
}

treap merge(treap a, treap b)
{
	a = fix(a);
	b = fix(b);
	if(!a) return b;
	if(!b) return a;
	if(a->y > b->y)
	{
		a->r = merge(a->r, b);
		return fix(a);
	}
	else
	{
		b->l = merge(a, b->l);
		return fix(b);
	}
}

struct comp
{
	li cur_sum;
	int beg;
	li treap_sum;
	treap t;
	
	void upd()
	{
		cur_sum = treap_sum + beg * 1ll * getSum(t);
	}
	
	void insert(int bi)
	{
		ptt p = split(t, bi);
		treap_sum += getSum(p.x) + getSiz(p.y) * 1ll * bi;
		t = merge(p.x, merge(new node(bi, rnd(), bi, 1, NULL, NULL), p.y));
		upd();
	}
	
	void fill_treap(treap t)
	{
		if(!t) return;
		insert(t->x);
		fill_treap(t->l);
		fill_treap(t->r);
	}
};

comp merge(comp a, comp b)
{
	if(getSiz(a.t) < getSiz(b.t))
		swap(a, b);
	a.beg = min(a.beg, b.beg);
	a.fill_treap(b.t);
	delete b.t;
	a.upd();
	return a;
}

set<int> free_pos;

const int N = 400043;

int p[N];
int siz[N];
comp cc[N];

li start_sum = 0;
li end_sum = 0;

int get(int x)
{
	return (p[x] == x ? x : (p[x] = get(p[x])));
}

void merge(int x, int y)
{
	x = get(x);
	y = get(y);
	if(x == y) return;
	if(siz[x] < siz[y]) swap(x, y);
	end_sum -= cc[x].cur_sum;
	end_sum -= cc[y].cur_sum;
	p[y] = x;
	siz[x] += siz[y];
	cc[x] = merge(cc[x], cc[y]);
	end_sum += cc[x].cur_sum;
}

void process(int ai, int bi)
{
	start_sum += ai * 1ll * bi;
	int pos = *free_pos.lower_bound(ai);
	free_pos.erase(pos);
	siz[pos] = 1;
	p[pos] = pos;
	cc[pos].beg = pos;
	cc[pos].insert(bi);
	end_sum += cc[pos].cur_sum;
	if(!free_pos.count(pos - 1))
		merge(pos, pos - 1);
	if(!free_pos.count(pos + 1))
		merge(pos, pos + 1);
	printf("%lld\n", end_sum - start_sum);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
    int n;
    scanf("%d", &n);
  	for(int i = 0; i < N; i++)
  		free_pos.insert(i);
	for(int i = 0; i < n; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		process(a, b);
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

	int n, m;
	cin >> n >> m;
	
	int r = 0;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		
		r += x;
		cout << r / m << ' ';
		r %= m;
	}
	cout << '\n';
	
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 1000 + 7;

int pr[N];
bool ok[N];

int main() {
	int n, m, q;
	scanf("%d%d%d", &n, &m, &q);
	string s, t;
	static char buf[N];
	scanf("%s", buf);
	s = buf;
	scanf("%s", buf);
	t = buf;
	
	pr[0] = 0;
	forn(i, n - m + 1){
		bool fl = true;
		forn(j, m)
			if (s[i + j] != t[j])
				fl = false;
		ok[i] = fl;
		pr[i + 1] = pr[i] + ok[i];
	}
	for (int i = max(0, n - m + 1); i < n; ++i){
		pr[i + 1] = pr[i];
	}
	
	forn(i, q){
		int l, r;
		scanf("%d%d", &l, &r);
		--l, r -= m - 1;
		printf("%d\n", r >= l ? pr[r] - pr[l] : 0);
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 300 * 1000 + 9;

int n;
int a[2][N];
long long sum123[2][N];
long long sum321[2][N];
long long sum111[2][N];

int main() {
	//freopen("input.txt", "r", stdin);
	
	scanf("%d", &n);
	for(int i = 0; i < 2; ++i)
		for(int j = 0; j < n; ++j)
			scanf("%d", &a[i][j]);
	
	for(int i = 0; i < 2; ++i)
		for(int j = n - 1; j >= 0; --j){
			sum123[i][j] = sum123[i][j + 1] + (j + 1) * 1LL * a[i][j];
			sum321[i][j] = sum321[i][j + 1] + (n - j) * 1LL * a[i][j];
			sum111[i][j] = sum111[i][j + 1] + a[i][j];
		}
		
/*	for(int i = 0; i < 2; ++i)
		for(int j = n - 1; j >= 0; --j){
			cout << i << ' ' << j << " : ";
			cout << sum123[i][j] << "  " << sum321[i][j] << "  " << sum111[i][j] << endl;
		}			*/
		
	long long res = 0, sum = 0;
	for(int i = 0, j = 0; j < n; ++j, i ^= 1){
		long long nres = sum;
		nres += sum123[i][j] + j * 1LL * sum111[i][j];
		nres += sum321[i ^ 1][j] + (j + n) * 1LL * sum111[i ^ 1][j];
		res = max(res, nres);
		
		sum += a[i][j] * 1ll * (j + j + 1);
		sum += a[i ^ 1][j] * 1ll * (j + j + 2);
	}
	
	for(int j = 0; j < n; ++j) res -= a[0][j] + a[1][j];
	printf("%I64d\n", res);
	
    return 0;
}                             	

#include <bits/stdc++.h>
#include "testlib.h"

using namespace std;

const int N = 109;

int n, m;
int a[N], b[N];
int res[N][N];

int main() {
	int cur = 0;
	cin >> n >> m;
	for(int i = 0; i < n; ++i)
		cin >> a[i], cur ^= a[i];
	for(int i = 0; i < m; ++i)
		cin >> b[i], cur ^= b[i];
	
	if(cur != 0){
		puts("NO");
		return 0;
	}
	
	puts("YES");
	for(int i = 1; i < m; ++i) 
		cur ^= b[i];
	cur ^= a[0];
	
	cout << cur << ' ';
	for(int i = 1; i < m; ++i)
		cout << b[i] << ' ';
	cout << endl;
	for(int i = 1; i < n; ++i){
		cout << a[i] << ' ';
		for(int j = 1; j < m; ++j)
			cout << 0 << ' ';
		cout << endl;
	}
    return 0;
}                             	

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<li, li> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);
const double EPS = 1e-9;

const int N = 200 * 1000 + 555;

li sy, a, b;
int n, q;
pt s[N], p[N];

inline bool read() {
	if(!(cin >> sy >> a >> b))
		return false;
	assert(cin >> n);
	fore(i, 0, n)
		assert(scanf("%lld%lld", &s[i].x, &s[i].y) == 2);
	assert(cin >> q);
	fore(i, 0, q)
		assert(scanf("%lld%lld", &p[i].x, &p[i].y) == 2);
	return true;
}

int getGE(ld x) {
	for(int pos = max(int(lower_bound(s, s + n, pt(li(x), -1)) - s) - 2, 0); pos < n; pos++)
		if(x <= s[pos].x)
			return pos;
	return n;
}

li ps[N];

li getSum(int l, int r) {
	li ans = r > 0 ? ps[r - 1] : 0;
	ans -= l > 0 ? ps[l - 1] : 0;
	return ans;
}

inline void solve() {
	fore(i, 0, n) {
		ps[i] = s[i].y - s[i].x;
		if(i > 0)
			ps[i] += ps[i - 1];
	}
	
	fore(i, 0, q) {
		ld lx = p[i].x + (a - p[i].x) * (ld(p[i].y) / (p[i].y - sy));
		ld rx = p[i].x + (b - p[i].x) * (ld(p[i].y) / (p[i].y - sy));
		
		int posL = getGE(lx);
		int posR = getGE(rx) - 1;
		
		ld sum = getSum(posL, posR);
		if(posL > 0)
			sum += max(ld(0.0), s[posL - 1].y - max((ld)s[posL - 1].x, lx));
		if(posR >= 0)
			sum += max(ld(0.0), min((ld)s[posR].y, rx) - s[posR].x);
		
		sum *= ld(p[i].y - sy) / p[i].y;
		printf("%.15f\n", double(sum));
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const long long INF64 = (long long)(1e18);
const int N = 1000 * 1000 + 13;

int n, m;
vector<pair<int, int>> g[N];
long long d[N];
int siz[N];
int tin[N], tout[N], T;
int pr[N];

void calc(int v, int p){
	pr[v] = p;
	tin[v] = T++;
	siz[v] = 1;
	for (auto it : g[v]){
		int u = it.first;
		int w = it.second;
		if (u == p) continue;
		d[u] = d[v] + w;
		calc(u, v);
		siz[v] += siz[u];
	}
	tout[v] = T++;
}

inline int isp(int v, int u){
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}

long long dif;
long long mn;

void dfs(int v, int p){
	dif = min(dif, max(0ll, -(mn - d[v])));
	if (p != -1 && pr[p] != -1)
		dif = min(dif, max(0ll, -(d[pr[p]] - d[v])));
	
	for (auto it : g[v]){
		int u = it.first;
		int w = it.second;
		if (u == p) continue;
		if (!isp(u, n - 1)){
			dif = min(dif, max(0ll, -(mn + w - d[v])));
			mn = max(mn, w + d[v]);
			if (p != -1)
				dif = min(dif, max(0ll, -(w - d[v] + d[p])));
		}
	}
	
	for (auto it : g[v]){
		int u = it.first;
		if (u == p) continue;
		if (isp(u, n - 1))
			dfs(u, v);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	forn(i, n - 1){
		int v, u, w;
		scanf("%d%d%d", &v, &u, &w);
		--v, --u;
		g[v].push_back(make_pair(u, w));
		g[u].push_back(make_pair(v, w));
	}
	
	T = 0;
	calc(0, -1);
	
	long long cur = d[n - 1];
	dif = INF64;
	mn = -INF64;
	
	forn(i, n)
		if (!isp(i, n - 1) && siz[i] > 1)
			dif = 0;
	
	if (dif > 0)
		dfs(0, -1);
	
	forn(i, m){
		int x;
		scanf("%d", &x);
		printf("%lld\n", min(cur, cur - dif + x));
	}
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

vector<vector<pair<int, int> > > g;
vector<long long> d;
vector<long long> d1;
vector<long long> dn;

int n, q;

bool read()
{
	scanf("%d %d", &n, &q);
	g.resize(n);
	d.resize(n);
	for(int i = 0; i < n - 1; i++)
	{
		int x, y, w;
		scanf("%d %d %d", &x, &y, &w);
		--x;
		--y;
		g[x].push_back(make_pair(y, w));
		g[y].push_back(make_pair(x, w));
	}
	return true;
}

void dfs(int x, int p = -1, long long dist = 0)
{
	d[x] = dist;
	for (auto e : g[x])
		if (p != e.first)
			dfs(e.first, x, e.second + dist);
}

void solve()
{
	dfs(0);
	d1 = d;
	dfs(n - 1);
	dn = d;
	set<pair<long long, int> > dists_n;
	vector<pair<long long, int> > order;
	for(int i = 0; i < n; i++)
	    order.push_back(make_pair(d1[i] - dn[i], i));
	sort(order.begin(), order.end());
	for(int i = 0; i < n; i++)
	    dists_n.insert(make_pair(dn[i], i));
	vector<int> pos(n);
	for(int i = 0; i < n; i++)
		pos[order[i].second] = i;
	long long T = (long long)(1e18);
	for(int i = 0; i < n; i++)
	{
		int v = order[i].second;
		dists_n.erase(make_pair(dn[v], v));
		for (auto e : g[v])
			if (pos[e.first] > pos[v])
				dists_n.erase(make_pair(dn[e.first], e.first));
		if (!dists_n.empty())
			T = min(T, d1[n - 1] - d1[v] - dists_n.rbegin()->first);
		for (auto e : g[v])
			if (pos[e.first] > pos[v])
				dists_n.insert(make_pair(dn[e.first], e.first));
	}
	for(int i = 0; i < q; i++)
	{
		int x;
		scanf("%d", &x);
		printf("%lld\n", d1[n - 1] - max(0ll, T - x));
	}
}

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	if (read())
	{
		solve();
	}
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<li, li> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);

const int N = 200 * 1000 + 555;
int n; li x, y;
li a[N];

inline bool read() {
	if(!(cin >> n >> x >> y))
		return false;
	fore(i, 0, n)
		assert(scanf("%lld", &a[i]) == 1);
	return true;
}

li gcd(li a, li b) {
	while(a > 0) {
		b %= a;
		swap(a, b);
	}
	return b;
}

vector<pt> factorize(li v) {
	vector<pt> f;
	for(li x = 2; x <= 1'000'000 && x * x <= v; x++) {
		int cnt = 0;
		while(v % x == 0)
			v /= x, cnt++;
		if(cnt > 0)
			f.emplace_back(x, cnt);
	}
	if(v > 1) {
		for(li s = max(1ll, (li)sqrtl(v) - 2); s * s <= v; s++)
			if(s * s == v) {
				f.emplace_back(s, 2);
				v = 1;
				break;
			}
		if(v > 1) {
			vector<li> cnd(a, a + n);
			cnd.push_back(x);
			cnd.push_back(y);
			
			for(li c : cnd) {
				li g = gcd(v, c);
				if(g != 1 && g != v) {
					li a = g, b = v / g;
					if(a > b)
						swap(a, b);
						
					f.emplace_back(a, 1);
					f.emplace_back(b, 1);
					v = 1;
					break;
				}
			}
			if(v > 1)
				f.emplace_back(v, 1), v = 1;
		}
	}
	return f;
}

int d[(1 << 18) + 3];

inline void solve() {
	if(y % x != 0) {
		puts("0");
		return;
	}
	
	vector<pt> fy = factorize(y);
	vector<pt> fx;
	li cx = x;
	for(auto p : fy) {
		int cnt = 0;
		while(cx % p.x == 0)
			cx /= p.x, cnt++;
		fx.emplace_back(p.x, cnt);
	}
	
	vector<li> ps;
	vector<pt> bb;
	
	fore(i, 0, sz(fy)) {
		if(fx[i].y < fy[i].y) {
			ps.push_back(fy[i].x);
			bb.emplace_back(fx[i].y, fy[i].y);
		}
	}
	
	fore(i, 0, n) {
		if(a[i] % x != 0)
			continue;
		
		int mask = 0;
		li ca = a[i];
		fore(j, 0, sz(ps)) {
			int cnt = 0;
			while(ca % ps[j] == 0)
				ca /= ps[j], cnt++;
			assert(cnt >= bb[j].x);
			
			mask |= (cnt > bb[j].x) << j;
		}
		d[mask]++;
	}
	
	for(int i = 0; i < sz(ps); i++) {
		fore(mask, 0, 1 << sz(ps))
			if((mask >> i) & 1)
				d[mask] += d[mask ^ (1 << i)];
	}
	
	li ans = 0;
	fore(i, 0, n) {
		if(y % a[i] != 0)
			continue;
		
		int mask = 0;
		li ca = a[i];
		fore(j, 0, sz(ps)) {
			int cnt = 0;
			while(ca % ps[j] == 0)
				ca /= ps[j], cnt++;
			assert(cnt <= bb[j].y);
			
			mask |= (cnt < bb[j].y) << j;
		}
		ans += d[mask ^ ((1 << sz(ps)) - 1)];
	}
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;


int main() {
	int n;
	cin >> n;
	
	vector<string> a(n), b(n);
	forn(i, n) cin >> a[i];
	forn(i, n) cin >> b[i];
	
	map<string, int> cnta, cntb;
	forn(i, n) ++cnta[a[i]];
	forn(i, n) ++cntb[b[i]];
	
	int ans = n;
	for (auto it : cnta) ans -= min(it.second, cntb[it.first]);
	
	cout << ans << endl;
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int n, M;
vector<int> a;

inline bool read() {
	if(!(cin >> n >> M))
		return false;
	a.assign(n, 0);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	return true;
}

vector<int> f[2];

inline void solve() {
	a.insert(a.begin(), 0);
	a.push_back(M);
	
	f[0].assign(a.size(), 0);
	f[1].assign(a.size(), 0);
	
	for(int i = int(a.size()) - 2; i >= 0; i--) {
		f[0][i] = f[1][i + 1];
		f[1][i] = (a[i + 1] - a[i]) + f[0][i + 1];
	}
	
	int ans = f[1][0];
	for(int i = 0; i + 1 < int(a.size()); i++) {
		if(a[i + 1] - a[i] < 2)
			continue;
		
		int tp = (i & 1) ^ 1;
		int pSum = f[1][0] - f[tp][i];
		ans = max(ans, pSum + (a[i + 1] - a[i] - 1) + f[tp][i + 1]);
	}
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	if(read())
		solve();
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	scanf("%d", &n);
	vector<pair<long long, long long>> a(n);
	vector<long long> cval;
	for (auto &i : a) {
		scanf("%lld %lld", &i.first, &i.second);
		cval.push_back(i.first);
		cval.push_back(i.second + 1);
		
	}
	sort(cval.begin(), cval.end());
	cval.resize(unique(cval.begin(), cval.end()) - cval.begin());
	
	vector<int> cnt(2 * n);
	for (auto &i : a) {
		int posl = lower_bound(cval.begin(), cval.end(), i.first) - cval.begin();
		int posr = lower_bound(cval.begin(), cval.end(), i.second + 1) - cval.begin();
		++cnt[posl];
		--cnt[posr];
	}
	for (int i = 1; i < 2 * n; ++i)
		cnt[i] += cnt[i - 1];
		
	vector<long long> ans(n + 1);
	for (int i = 1; i < 2 * n; ++i)
		ans[cnt[i - 1]] += cval[i] - cval[i - 1];
	
	for (int i = 1; i <= n; ++i)
		printf("%lld ", ans[i]);
	puts("");
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1009;
const int MOD = 998244353;

int n;
int a[N];
int dp[N];
int C[N][N];

int main() {
	for(int i = 0; i < N; ++i){
		C[i][0] = C[i][i] = 1;
		for(int j = 1; j < i; ++j)
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
	}
	
	cin >> n;
	for(int i = 0; i < n; ++i)
		cin >> a[i];
	
	dp[n] = 1;
	for(int i = n - 1; i >= 0; --i){
		if(a[i] <= 0) continue;
		
		for(int j = i + a[i] + 1; j <= n; ++j){
				dp[i] += (dp[j] * 1LL * C[j - i - 1][a[i]]) % MOD;
				dp[i] %= MOD;
		}
	}

	int sum = 0;
	for(int i = 0; i < n; ++i){
		sum += dp[i];
		sum %= MOD;
	}
	cout << sum << endl;
	
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 500043;

vector<int> g[N];
vector<int> t[N];
int tin[N], tout[N], fup[N];
int p[N];
int T = 1;
int rnk[N];
vector<pair<int, int> > bridges;
int st;
int d[N];
int n, m;

int get(int x)
{
 	return (p[x] == x ? x : p[x] = get(p[x]));
}

void link(int x, int y)
{
 	x = get(x);
 	y = get(y);
 	if(x == y) return;
 	if(rnk[x] > rnk[y])
 		swap(x, y);
 	p[x] = y;
 	rnk[y] += rnk[x];	
}

int dfs(int x, int par = -1)
{
	tin[x] = T++;
	fup[x] = tin[x];
	for(auto y : g[x])
	{
	 	if(tin[y] > 0)
	 	{
	 		if(par != y)
	 			fup[x] = min(fup[x], tin[y]);
	 	}
	 	else
	 	{
	 	 	int f = dfs(y, x);
	 	 	fup[x] = min(fup[x], f);
	 	 	if(f > tin[x])
	 	 		bridges.push_back(make_pair(x, y));
	 	 	else
	 	 		link(x, y);
	 	}
	}
	tout[x] = T++;                                      
	return fup[x];
}      

void build()
{
 	for(auto z : bridges)
 	{
 	 	int x = get(z.first);
 	 	int y = get(z.second);
 	 	st = x;
 	 	t[x].push_back(y);
 	 	t[y].push_back(x);
 	}
}

pair<int, int> bfs(int x)
{
	for(int i = 0; i < n; i++)
		d[i] = n + 1;
	d[x] = 0;
	queue<int> q;
	q.push(x);
	int last = 0;
	while(!q.empty())
	{
	 	last = q.front();
	 	q.pop();
	 	for(auto y : t[last])
	 		if(d[y] > d[last] + 1)
	 		{
	 		 	d[y] = d[last] + 1;
	 		 	q.push(y);
	 		}
	}
	return make_pair(last, d[last]);
}

int main()
{                
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++)
		rnk[i] = 1, p[i] = i;
	for(int i = 0; i < m; i++)
	{
	 	int x, y;
	 	scanf("%d %d", &x, &y);
	 	--x;
	 	--y;
	 	g[x].push_back(y);
	 	g[y].push_back(x);
	}
	dfs(0);
	build();
	pair<int, int> p1 = bfs(st);
	pair<int, int> p2 = bfs(p1.first);
	printf("%d\n", p2.second);
}

#include<bits/stdc++.h>

using namespace std;

const int INF = int(1e9);
const int N = 500001;

typedef pair<int, int> pt;

#define x first
#define y second
#define mp make_pair

struct node
{
 	pt val;
	node* l;
	node* r;
	node() : val(mp(INF, 0)), l(NULL), r(NULL) {};
	node(node* l, node* r) 
	{
	 	this->val = min(l->val, r->val);
		this->l = l;
		this->r = r;
	}
	node(int pos, int val)
	{
	 	this->val = mp(val, pos);
		this->l = NULL;
		this->r = NULL;
	}
};

typedef node* stree;

pt query(stree t, int l, int r, int L, int R)
{
 	if(L >= R)
		return mp(INF, 0);
	if(l == L && r == R)
		return t->val;
	int mid = (l + r) >> 1;
	pt q1 = query(t->l, l, mid, L, min(mid, R));
	pt q2 = query(t->r, mid, r, max(mid, L), R);
	return min(q1, q2);
}

stree update(stree t, int l, int r, int pos, int val)
{
 	if(l == r - 1)
		return new node(pos, val);
	else
	{
	 	int mid = (l + r) >> 1;
		if(pos < mid)
			return new node(update(t->l, l, mid, pos, val), t->r);
		else
			return new node(t->l, update(t->r, mid, r, pos, val));
	}
}

stree build(int l, int r)
{
 	if(l == r - 1)
		return new node(l, INF);
	else
	{
	 	int mid = (l + r) >> 1;
		return new node(build(l, mid), build(mid, r));
	}
}

int main()
{
 	int n;
	scanf("%d", &n);
	vector<int> a(n);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);

	vector<int> left(n);
	map<int, int> last;
	for(int i = 0; i < n; i++)
	{
	 	if(!last.count(a[i]))
			left[i] = -1;
		else
			left[i] = last[a[i]];
		last[a[i]] = i;
	}

	vector<stree> T(n + 1);
	T[0] = build(0, n);
	for(int i = 0; i < n; i++)
	{
		stree cur = T[i];
		if(left[i] != -1)
			cur = update(cur, 0, n, left[i], INF);
		cur = update(cur, 0, n, i, left[i]);
		T[i + 1] = cur;	
	}                      
	
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++)
	{
	 	int l, r;
		scanf("%d %d", &l, &r);
		--l;
		pt ans = query(T[r], 0, n, l, r);
		if(ans.x < l)
			printf("%d\n", a[ans.y]);
		else
			printf("0\n");
	}
}

#include<bits/stdc++.h>

using namespace std;

const int INF = int(1e9);
const int N = 500001;

typedef pair<int, int> pt;

#define x first
#define y second
#define mp make_pair

const int M = 60 * N;

pt bufp[M];
int lf[M];
int rg[M];
int szt = 0;

int newnode(pt val)
{
	bufp[szt] = val;
	return szt++;
}

int newnode(int l, int r)
{
 	lf[szt] = l;
	rg[szt] = r;
	if(bufp[l].x < bufp[r].x)
	    bufp[szt] = bufp[l];
	else
	    bufp[szt] = bufp[r];
	return szt++;
}

pt curans;

void query(int t, int l, int r, int L, int R)
{
 	if(L >= R)
		return;
	if(l == L && r == R)
	{
	    if(bufp[t].x < curans.x)
	        curans = bufp[t];
	    return;
	}
	int mid = (l + r) >> 1;
	query(lf[t], l, mid, L, min(mid, R));
	query(rg[t], mid, r, max(mid, L), R);
}

int update(int t, int l, int r, int pos, int val)
{
 	if(l == r - 1)
		return newnode(mp(val, pos));
	else
	{
	 	int mid = (l + r) >> 1;
		if(pos < mid)
			return newnode(update(lf[t], l, mid, pos, val), rg[t]);
		else
			return newnode(lf[t], update(rg[t], mid, r, pos, val));
	}
}

int build(int l, int r)
{
 	if(l == r - 1)
		return newnode(mp(INF, l));
	else
	{
	 	int mid = (l + r) >> 1;
		return newnode(build(l, mid), build(mid, r));
	}
}

int last[N];

int main()
{
 	int n;
	scanf("%d", &n);
	vector<int> a(n);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);

	vector<int> left(n);
	for(int i = 0; i < N; i++)
	    last[i] = -1;
	for(int i = 0; i < n; i++)
	{
	 	left[i] = last[a[i]];
		last[a[i]] = i;
	}

	vector<int> T(n + 1);
	T[0] = build(0, n);
	for(int i = 0; i < n; i++)
	{
		int cur = T[i];
		if(left[i] != -1)
			cur = update(cur, 0, n, left[i], INF);
		cur = update(cur, 0, n, i, left[i]);
		T[i + 1] = cur;	
	}                      
	
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++)
	{
	 	int l, r;
		scanf("%d %d", &l, &r);
		--l;
		curans = mp(INF, 0);
		query(T[r], 0, n, l, r);
		if(curans.x < l)
			printf("%d\n", a[curans.y]);
		else
			printf("0\n");
	}
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 
#define x first
#define y second

const int N = 500 * 1000 + 13;
const int INF = 1e9;

pair<pair<int, int>, int> t[4 * N];

void build(int v, int l, int r){
	if (l == r - 1){
		t[v] = make_pair(make_pair(INF, INF), l);
		return;
	}
	
	int m = (l + r) / 2;
	
	build(v * 2, l, m);
	build(v * 2 + 1, m, r);
	
	t[v] = min(t[v * 2], t[v * 2 + 1]);
}

void update(int v, int l, int r, int pos, int prv, int nxt){
	if (l == r - 1){
		t[v].x = make_pair(nxt, prv);
		return;
	}
	
	int m = (l + r) / 2;
	
	if (pos < m)
		update(v * 2, l, m, pos, prv, nxt);
	else
		update(v * 2 + 1, m, r, pos, prv, nxt);
	
	t[v] = min(t[v * 2], t[v * 2 + 1]);
}

pair<pair<int, int>, int> get(int v, int l, int r, int L, int R){
	if (L >= R)
		return make_pair(make_pair(INF, INF), -1);
	
	if (l == L && r == R)
		return t[v];
	
	int m = (l + r) / 2;
	
	return min(get(v * 2, l, m, L, min(m, R)), get(v * 2 + 1, m, r, max(m, L), R));
}

int n, m;
int a[N];
pair<pair<int, int>, int> q[N];
int pos[N];
int ans[N];

bool comp(const pair<pair<int, int>, int> &a, const pair<pair<int, int>, int> &b){
	return a.x.y < b.x.y;
}

int main() {
	memset(pos, -1, sizeof(pos));
	scanf("%d", &n);
	forn(i, n) scanf("%d", &a[i]);
	scanf("%d", &m);
	forn(i, m){
		scanf("%d%d", &q[i].x.x, &q[i].x.y);
		--q[i].x.x, --q[i].x.y;
		q[i].y = i;
	}
	sort(q, q + m, comp);
	
	build(1, 0, n);
	int lst = -1;
	forn(i, m){
		int l = q[i].x.x;
		int r = q[i].x.y;
		
		for (int j = lst + 1; j <= r; ++j){
			if (pos[a[j]] != -1)
				update(1, 0, n, pos[a[j]], -INF, j);
			update(1, 0, n, j, pos[a[j]], -INF);
			pos[a[j]] = j;
		}
		
		auto it = get(1, 0, n, l, r + 1);
		
		if (it.y == -1 || it.x.x != -INF || it.x.y >= l){
			ans[q[i].y] = 0;
		}
		else{
			ans[q[i].y] = a[it.y];
		}
		
		lst = r;
	}
	
	forn(i, m)
		printf("%d\n", ans[i]);
	
	return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 
#define x first
#define y second

const int N = 500 * 1000 + 13;
const int P = 800;
const int INF = 1e9;

bool comp(const pair<pair<int, int>, int> &a, const pair<pair<int, int>, int> &b){
	int num = a.x.x / P;
	if (num != b.x.x / P)
		return a.x.x < b.x.x;
	if (num & 1)
		return a.x.y < b.x.y;
	return a.x.y > b.x.y;
}

int val[N];
int cnt[N];
int bl[P];
int tot;

inline void add(int x){
	++cnt[x];
	if (cnt[x] == 1){
		++val[x];
		++bl[x / P];
		++tot;
	}
	else if (cnt[x] == 2){
		--val[x];
		--bl[x / P];
		--tot;
	}
}

inline void sub(int x){
	--cnt[x];
	if (cnt[x] == 1){
		++val[x];
		++bl[x / P];
		++tot;
	}
	else if (cnt[x] == 0){
		--val[x];
		--bl[x / P];
		--tot;
	}
}

int get(){
	if (tot == 0) 
		return 0;
	
	forn(i, P){
		if (bl[i] > 0){
			for (int j = i * P;; ++j){
				if (val[j]){
					return j;
				}
			}
		}
	}
	
	assert(false);
}

int n, m;
int a[N], ans[N];
pair<pair<int, int>, int> q[N];

int main() {
	scanf("%d", &n);
	forn(i, n) scanf("%d", &a[i]);
	scanf("%d", &m);
	forn(i, m){
		scanf("%d%d", &q[i].x.x, &q[i].x.y);
		--q[i].x.x, --q[i].x.y;
		q[i].y = i;
	}
	sort(q, q + m, comp);
	
	int l = 0, r = -1;
	
	forn(i, m){
		int L = q[i].x.x;
		int R = q[i].x.y;
		
		while (r < R){
			++r;
			add(a[r]);
		}
		
		while (r > R){
			sub(a[r]);
			--r;
		}
		
		while (l > L){
			--l;
			add(a[l]);
		}
		
		while (l < L){
			sub(a[l]);
			++l;
		}
		
		ans[q[i].y] = get();
	}
	
	forn(i, m)
		printf("%d\n", ans[i]);
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
	return out << "(" << p.x << ", " << p.y << ")";
}

template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
	out << "[";
	fore(i, 0, sz(v)) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}

const int M = 400 * 1000 + 555;
const int N = 300 * 1000 + 555;
const int LOGN = 19;

int n, m, a[N];
vector<pt> g[N];

inline bool read() {
	if(!(cin >> n >> m))
		return false;
	fore(i, 0, n)
		assert(scanf("%d", &a[i]) == 1);
	fore(i, 0, n - 1) {
		int u, v, w;
		assert(scanf("%d%d%d", &u, &v, &w) == 3);
		u--, v--;
		
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}
	fore(i, 0, n)
		sort(all(g[i]));
	return true;
}

int tin[N], tout[N], T = 0;
int p[N][LOGN];

int h[N];
li d1[N];

void calc1(int v, int pr) {
	tin[v] = T++;
	p[v][0] = pr;
	fore(st, 1, LOGN)
		p[v][st] = p[p[v][st - 1]][st - 1];
	
	d1[v] = a[v];
	fore(i, 0, sz(g[v])) {
		int to = g[v][i].x;
		int w = g[v][i].y;
		
		if(to == pr)
			continue;

		h[to] = h[v] + 1;
		calc1(to, v);
		d1[v] += max(0ll, d1[to] - 2ll * w);
	}
	tout[v] = T++;
}

li dp[N];
vector<li> dto[N];

void calcRRT(int v) {
	dp[v] = a[v];
	dto[v].assign(sz(g[v]), 0ll);
	
	fore(i, 0, sz(g[v])) {
		int to = g[v][i].x;
		int w = g[v][i].y;
		
		li curVal = max(0ll, d1[to] - 2ll * w);
		dp[v] += curVal;
		dto[v][i] = curVal;
	}
	
	fore(i, 0, sz(g[v])) {
		int to = g[v][i].x;
		if(h[to] < h[v])
			continue;
		
		li tmp = d1[v];
		d1[v] = dp[v] - dto[v][i];
		calcRRT(to);
		d1[v] = tmp;
	}
}

inline bool isP(int l, int v) {
	return tin[l] <= tin[v] && tout[v] <= tout[l];
}

int lca(int u, int v) {
	if(isP(u, v)) return u;
	if(isP(v, u)) return v;
	
	for(int st = LOGN - 1; st >= 0; st--)
		if(!isP(p[v][st], u))
			v = p[v][st];
	return p[v][0];
}


li getDto(int v, int to) {
	int pos = int(lower_bound(all(g[v]), pt(to, -1)) - g[v].begin());
	if(pos >= sz(g[v]) || g[v][pos].x != to)
		return 0;
	return dto[v][pos];
}

li f[N];

inline void inc(int pos, li val) {
	for(; pos < N; pos |= pos + 1)
		f[pos] += val;
}

inline li sum(int pos) {
	li ans = 0;
	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
		ans += f[pos];
	return ans;
}

inline li getSum(int l, int r) {
	return sum(r) - sum(l);
}

li ans[M];
vector<pt> qs[N];

void calcAns(int v) {
	li vAdd = dp[v] - getDto(v, p[v][0]);
	inc(h[v], vAdd);
	
	for(pt &q : qs[v]) {
		int up = q.x, id = q.y;
		ans[id] += getSum(h[up] - 1, h[v]) + getDto(up, p[up][0]);
	}
	
	fore(i, 0, sz(g[v])) {
		int to = g[v][i].x;
		int w = g[v][i].y;
		if(h[to] < h[v])
			continue;
		
		li curSub = dto[v][i] + w;
		inc(h[v], -curSub);
		
		calcAns(to);
		inc(h[v], +curSub);
	}
	inc(h[v], -vAdd);
}

inline void solve() {
	T = 0;
	h[0] = 0;
	calc1(0, 0);
	calcRRT(0);
	
	fore(i, 0, m) {
		int u, v;
		assert(scanf("%d%d", &u, &v) == 2);
		u--, v--;
		
		int l = lca(u, v);		
		ans[i] = -dp[l];
		
		qs[u].emplace_back(l, i);
		qs[v].emplace_back(l, i);
	}
	
	calcAns(0);
	fore(i, 0, m)
		printf("%lld\n", ans[i]);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

Hint: When does some vowel stay in string?

Hint 1: It's never profitable to go back. No prizes left where you have already gone.

Hint: At first we will solve the problem mentioned in the statement. The formula is . Firstly, each submatrix k × k should have at least one row with zero in it. Exactly non-intersecting submatrices fit in matrix n × k. The same with the columns. So you should have at least this amount squared zeros.

The function of the path length is not that different from the usual one. You can multiply edge weights by two and run Dijkstra in the following manner. Set dist_i = a_i for all and push these values to heap. When finished, dist_i will be equal to the shortest path.

Model solution

Hint 1: Count the number of times each number appears in the sum of all f_a.

Hint 2: Try to find a sufficient and necessary condition that a_i appears in f_a of a permutation.

More hints

Hint 3: Prove that a_i appears if and only if all elements appearing before it are strictly less than it (other than the largest element). And then try to solve the problem first in O(n²).

Now try to solve to simplify your solution with O(n²).

Solution

It is easy to see that i-th element appears in f_a if and only if all elements appearing before it in the array are less than it, so if we define l_i as the number of elements less than a_i the answer will be equal to:

By determining the index of a_i, if it is on the index j then we have to choose j - 1 of the l_i elements smaller than it and then permuting them and then permuting the other elements. We can find all l_i with complexity of O(n log n). If we were to implement this, the complexity would equal to O(n²).

Now let's make our formula better. So let's open it like so:

and then it equals to:

and now let's take out the l_i! ,

now let's multiply the inside the first sigma by and the second sigma by (n - l_i - 1)! and it gets equal to:

and it is easy to see it equals to:

and using the fact that

it will equal to:

So the final answer will equal to:

of which can be easily implemented in O(n log n). Make sure to not add the answer for maximum number in the sequence.

There is also another solution that you can read here.

Model solution

Let's denote n = |s|.

Hint: There is a simple solution: dp[m][mask] — best answer if we considered first m characters of the string and a mask of erased substrings. However, storing a string as a result of each state won't fit neither into time limit nor into memory limit. Can we make it faster?

This is a more complex version of problem G from Educational Round 27. You can find its editorial here.

To solve the problem we consider now, you have to use a technique known as dynamic connectivity. Let's build a segment tree over queries: each vertex of the segment tree will contain a list of all edges existing in the graph on the corresponding segment of queries. If some edge exists from query l to query r, then it's like an addition operation on segment [l, r] in segment tree (but instead of addition, we insert this edge into the list of edges on a segment, and we make no pushes). Then if we write some data structure that will allow to add an edge and rollback operations we applied to the structure, then we will be able to solve the problem by DFS on segment tree: when we enter a vertex, we add all edges in the list of this vertex; when we are in a leaf, we calculate the required answer for the corresponding moment of time; and when we leave a vertex, we rollback all changes we made there.

What data structure do we need? Firstly, we will have to use DSU maintaining the distance to the leader (to maintain the length of some path between two vertices). Don't use path compression, this won't work well since we have to do rollbacks.

Secondly, we have to maintain the base of all cycles in the graph (since the graph is always connected, it doesn't matter that some cycles may be unreachable: by the time we get to leaves of the segment tree, these cycles will become reachable, so there's no need to store a separate base for each component). A convenient way to store the base is to make an array of 30 elements, initially filled with zeroes (we denote this array as a). i-th element of the array will denote some number in a base such that i-th bit is largest in the number. Adding some number x to this base is really easy: we iterate on bits from 29-th to 0-th, and if some bit j is equal to 1 in x, and a[j] ≠ 0, then we just set (let's call this process reduction, we will need it later). If we get 0 after doing these operations, then the number we tried to add won't affect the base, and we don't need to do anything; otherwise, let k be the highmost bit equal to 1 in x, and then we set a[k]:  = x.

This method of handling the base of cycles also allows us to answer queries of type 3 easily: firstly, we pick the length of some path from DSU (let it be p), and secondly, we just apply reduction to p, and this will be our answer.

Model solution