#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;
}

Подсказка: Когда гласная остается в строке?

Подсказка 1: Никогда не выгодно возвращаться. Там, где вы прошли, не осталось призов.

Подсказка: Для начала решим задачу, обозначенную в условии. Формула — . Каждая подматрица k × k должна включать в себя хотя бы одну строку с нулем. Ровно непересекающихся подматриц помещаются в матрицу n × k. То же для столбцов. Тогда нельзя выбрать меньше, чем это значение в квадрате, нулей.

Функция длины пути практически не отличается от традиционной. Можно домножить веса ребер на два и запустить алгоритм Дейкстры следующим образом. Установим dist_i = a_i для всех и добавим все эти значение в кучу. Когда алгоритм завершит работу, dist_i будет равно кратчайшему пути.

Исходный код решения

Подсказка 1: Посчитайте, сколько раз каждое число встречается в сумме всех f_a.

Подсказка 2: Попробуйте подобрать точные критерии того, что a_i войдет в f_a для какой-либо перестановки.

Больше подсказок

Подсказка 3: Докажите, что a_i входит тогда и только тогда, когда все элементы до нее строго меньше (кроме максимума в массиве). Теперь попробуйте решить за O(n²).

Попытайтесь упростить решение и сделать его быстрее.

Решение

Легко заметить, что i-й элемент входит в f_a тогда и только тогда, когда все элементы до нее строго меньше, поэтому если определим l_i как количество элементов меньших a_i, то ответ будет равен:

Взглянем на позицию a_i, если он на позиции j, то требуется выбрать j - 1 из l_i меньших элементов, расставить их каким-то образом и расставить остальные. Можем найти все l_i за O(n log n). Если написать ровно это, то асимптотика будет O(n²).

Попробуем улучшить формулу. Раскроем как:

теперь это равно:

и вынесем l_i!,

теперь домножим первую сумму на и вторую сумму на (n - l_i - 1)!, оно становится равно:

и легко заметить, что это же равно:

Используем тот факт, что

это равно:

Тогда окончательный ответ равен:

который может быть легко посчитан за O(n log n). Не забудьте, что считать ответ для максимального числа не нужно.

Также есть другое решение, которое можно прочитать тут.

Исходный код решения

В разборе обозначим n = |s|.

Подсказка: Есть простое решение за время : dp[m][mask] — лучший ответ, если мы рассмотрели первые m символов строки, а маска обозначает, подстроки какой длины мы удаляли. Однако хранить строку в каждом состоянии не позволяют ни ограничения по времени, ни ограничения по памяти. Как можно улучшить это решение?

Это усложнённая версия задачи G с Educational Round 27. Её разбор можно найти здесь.

Чтобы решить нашу текущую задачу, воспользуемся известным методом динамической связности. Построим дерево отрезков по запросов: каждая вершина ДО будет содержать список всех рёбер, присутствующих в графе на соответствующем отрезке запросов. Если некоторое ребро присутствует с запроса l по запрос r, то его можно добавить по аналогии с прибавлением на отрезке [l, r] в ДО (но вместо прибавления мы вставляем ребро в список, и мы не делаем никаких проталкиваний, которые обычно делаются в ДО с отложенными операциями). Если мы теперь напишем некоторую структуру, которая может добавлять ребро и откатывать изменения, можно решить задачу, обойдя дерево отрезков обходом в глубину: когда мы входим в вершину, добавим все рёбра в списке этой вершины; когда мы в листе, посчитаем ответ для запроса в этом листе (если он там есть); и когда мы покидаем вершину, мы откатываем сделанные в ней изменения.

Какая структура данных нам понадобится? Во-первых, DSU с поддержкой расстояния до лидера (чтобы находить некоторый путь между двумя вершинами). Не стоит использовать сжатие путей, из-за откатов оно не будет ускорять операции в DSU.

Во-вторых, надо как-то поддерживать базис циклов в графе (так как граф всегда связный, то нет смысла поддерживать базис циклов для каждой компоненты отдельно). Удобный способ хранения базиса — использовать массив из 30 элементов, изначально заполненный нулями (обозначим этот массив как a). i-элемент массива будет обозначать некоторое число в базисе, в котором i-й бит является максимальным среди всех взведённых битов. Тогда можно очень просто добавить в базис некоторое число x: переберём все биты от 29-го до 0-го, и если некоторый бит j равен 1 в числе x, и a[j] ≠ 0, то присвоим (назовём этот процесс сокращением, он нам ещё потребуется). Если после этого мы получим 0, то число уже является линейной комбинацией базиса; иначе, пусть k — наибольший бит, равный 1 в x, нам нужно просто присвоить a[k]:  = x.

Такой способ хранения базиса также позволяет очень просто отвечать на запросы 3 типа: сначала возьмём длину пути из DSU (пусть эта длина равна p), а затем просто сократим p, и это и будет ответом.

Исходный код решения