#include <bits/stdc++.h>

using namespace std;

const int INF = int(2e9) + 99;

int n, x, y, d;

int dist(int x, int y){
	return (abs(x - y) + (d - 1)) / d;
}

int main() {
	
	int t;
	cin >> t;
	for(int i = 0; i < t; ++i){
    	cin >> n >> x >> y >> d;
    	
    	int len = abs(x - y);
    	int res = INF;
    	
    	if(len % d == 0) 
    		res = min(res, dist(x, y));
    	
    	len = y - 1;
    	if(len % d == 0)
    		res = min(res, dist(x, 1) + dist(1, y));
    	
    	len = n - y;
    	if(len % d == 0)
    		res = min(res, dist(x, n) + dist(n, y));
    		
    	if(res == INF)
    		res = -1;
    	
    	cout << res << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n;
string s;

int main() {
	
	cin >> n >> s;
	
	vector <int> l(n), r(n);
	for(int i = 0; i < n; ++i){
		if(s[i] == 'G'){
			l[i] = 1;
			if(i > 0) l[i] += l[i - 1];
		}
	}
	for(int i = n - 1; i >= 0; --i){
		if(s[i] == 'G'){
			r[i] = 1;
			if(i + 1 < n) r[i] += r[i + 1];
		}
	}
	
	
	int res = 0;
	int cntG = 0;
	for(int i = 0; i < n; ++i)
			cntG += s[i] == 'G';
			
	for(int i = 0; i < n; ++i){
		if(s[i] == 'G') continue;
		int nres = 1;
		if(i > 0) nres += l[i - 1];
		if(i + 1 < n) nres += r[i + 1];
		res = max(res, nres);
	}
	
	res = min(res, cntG);
	if(cntG == n) res = cntG;
	cout << res << 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 sz(a) int((a).size())

int n, m;
vector<int> s, r;

inline bool read() {
	if(!(cin >> n >> m))
		return false;
	s.assign(n, 0);
	r.assign(n, 0);
	
	fore(i, 0, n) {
		assert(cin >> s[i] >> r[i]);
		s[i]--;
	}
	return true;
}

vector< vector<int> > subs;

inline void solve() {
	subs.assign(m + 1, vector<int>());
	
	fore(i, 0, n)
		subs[s[i]].push_back(r[i]);
		
	fore(id, 0, sz(subs)) {
		sort(subs[id].begin(), subs[id].end());
		reverse(subs[id].begin(), subs[id].end());
	}
	
	vector<int> mx(n + 5, 0);
	fore(id, 0, sz(subs)) {
		int curSum = 0;
		fore(i, 0, sz(subs[id])) {
			curSum += subs[id][i];
			if(curSum < 0)
				break;
				
			mx[i + 1] += curSum;
		}
	}
	
	cout << *max_element(mx.begin(), mx.end()) << 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;

const int N = 1000 + 7;

int n;
int a[N];

int main() {
	scanf("%d", &n);
	forn(i, n)
		scanf("%d", &a[i]);
	
	int sum = 0;
	forn(i, n)
		sum += a[i];
	
	if (sum < 2 * n - 2){
		puts("NO");
		return 0;
	}
	
	vector<int> ones;
	forn(i, n) if (a[i] == 1){
		a[i] = 0;
		ones.push_back(i);
	}
	
	int t = ones.size();
	int dm = (n - t) - 1 + min(2, t);
	printf("YES %d\n%d\n", dm, n - 1);
	
	int lst = -1;
	if (!ones.empty()){
		lst = ones.back();
		ones.pop_back();
	}
	
	forn(i, n){
		if (a[i] > 1){
			if (lst != -1){
				--a[lst];
				--a[i];
				printf("%d %d\n", lst + 1, i + 1);
			}
			lst = i;
		}
	}
	
	for (int i = n - 1; i >= 0; --i){
		while (!ones.empty() && a[i] > 0){
			--a[i];
			printf("%d %d\n", i + 1, ones.back() + 1);
			ones.pop_back();
		}
	}
	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())

const int INF = int(1e9);

int n, c;
vector<int> a;

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

vector<int> cntC;

int getCnt(int l, int r) {
	return cntC[r] - cntC[l];
}

vector< vector<int> > segs;
vector<int> lst;

int maxSegment(const vector<int> &s) {
	int mx = -INF;
	
	int bal = 0;
	fore(i, 0, sz(s)) {
		bal = max(0, bal + s[i]);
		mx = max(mx, bal);
	}
	return mx;
}

inline void solve() {
	cntC.assign(n + 1, 0);
	fore(i, 0, n)
		cntC[i + 1] = cntC[i] + (a[i] == c);
	
	int cntDif = *max_element(a.begin(), a.end()) + 1;
	segs.assign(cntDif, vector<int>());
	lst.assign(cntDif, -1);
	
	fore(i, 0, n) {
		segs[a[i]].push_back(-getCnt(lst[a[i]] + 1, i));
		lst[a[i]] = i;
		segs[a[i]].push_back(1);
	}
	fore(v, 0, cntDif)
		segs[v].push_back(-getCnt(lst[v] + 1, n));
		
	int ans = 0;
	fore(v, 0, cntDif) {
		if(v == c) continue;
		ans = max(ans, maxSegment(segs[v]));
	}
	
	cout << getCnt(0, n) + 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;

const int N = 500 + 7;
const int M = 11;
const int INF = 1e9;

struct node{
	int nxt[10];
	int cnt;
	node(){
		memset(nxt, -1, sizeof(nxt));
		cnt = 0;
	}
};

node trie[N];
int cnt;
int h[N];

void add(string s, int m){
	int cur = 0;
	forn(i, s.size()){
		int c = s[i] - '0';
		if (trie[cur].nxt[c] == -1){
			trie[cur].nxt[c] = cnt;
			h[cnt] = h[cur] + 1;
			++cnt;
		}
		cur = trie[cur].nxt[c];
	}
	trie[cur].cnt += m;
}

int n, k;

int dp[N][M][N];
int dp2[N][M][N][M];

int calc(int x, int rem, int k){
	if (dp[x][rem][k] != -1)
		return dp[x][rem][k];
	
	vector<int> ch;
	forn(i, 10) if (trie[x].nxt[i] != -1)
		ch.push_back(trie[x].nxt[i]);
	
	dp[x][rem][k] = INF;
	if (rem > 0)
		dp[x][rem][k] = min(dp[x][rem][k], calc(x, rem - 1, x));
	
	dp2[x][rem][k][ch.size()] = 0;
	for (int i = int(ch.size()) - 1; i >= 0; --i) forn(z, rem + 1)
		dp2[x][rem][k][i] = min(dp2[x][rem][k][i], calc(ch[i], z, k) + dp2[x][rem - z][k][i + 1]);
	
	dp[x][rem][k] = min(dp[x][rem][k], dp2[x][rem][k][0] + (h[x] - h[k]) * trie[x].cnt);
	
	return dp[x][rem][k];
}

int main() {
	trie[0] = node();
	cnt = 1;
	
	cin >> n >> k;
	forn(i, n){
		string s;
		int m;
		cin >> s >> m;
		add(s, m);
	}
	
	memset(dp, -1, sizeof(dp));
	
	forn(i, N) forn(j, M) forn(l, N) forn(t, M)
		dp2[i][j][l][t] = INF;
	
	int ans = calc(0, k, 0);
	
	cout << ans << endl;
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long li;

const int N = 2009;
const int INF = int(1e9) + 777;

struct edge{
	int to, f, c;
	edge () {}
	edge (int to, int f, int c) : to(to), f(f), c(c) {}
};

int n, m;
int s, t;
vector<edge> edges;
vector <int> g[N];
int u[N], cu;

void addEdge(int v, int to, int cap){

	g[v].push_back(edges.size());
	edges.push_back(edge(to, 0, cap));

	g[to].push_back(edges.size());
	edges.push_back(edge(v, 0, 0));
}

int dfs(int v, int need){
	if(v == t) return need;
	u[v] = cu;
	for(auto to : g[v]){
		edge &e = edges[to];
		if(u[e.to] != cu && e.c - e.f >= need){
			int add = dfs(e.to, need);
			if(add > 0){
				edges[to].f += add;
				edges[to ^ 1].f -= add;
				return add;
			}
		}
	}
	return 0;
}

li enlarge(int k){
	li res = 0;
	while(true){
		++cu;
		int add = dfs(s, k);
		res += add;
		if(add == 0) break;
	}
	return res;
}

li maxFlow(){
	li flow = 0;
	for(int k = (1 << 29); k > 0; k >>= 1){
		flow += enlarge(k);
	}
	return flow;
}

int main() {
	//freopen("input.txt", "r", stdin);
	int nn, mm;
	cin >> nn >> mm;
	n = nn + mm + 5;
	m = nn + mm + mm + mm + 5;
	s = n - 1, t = n - 2;
	
	for(int i = 0; i < nn; ++i){
		int a;
		cin >> a;
		addEdge(i + mm, t, a);
	}

	li sum = 0;
	for(int i = 0; i < mm; ++i){
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		sum += w;
		
		addEdge(s, i, w);
		addEdge(i, u + mm, INF);
		addEdge(i, v + mm, INF);
	}
	
	li fl = maxFlow();
	cout << sum - fl << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n;
	string s;
	cin >> n >> s;
	int pos = n - 1;
	for (int i = 0; i < n - 1; ++i) {
		if (s[i] > s[i + 1]) {
			pos = i;
			break;
		}
	}
	cout << s.substr(0, pos) + s.substr(pos + 1) << endl;
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

long long get(long long n){
	for (long long i = 2; i * i <= n; ++i)
		if (n % i == 0)
			return i;
	return n;
}

int main() {
	long long n;
	scanf("%lld", &n);
	long long cnt = 0;
	if (n % 2 != 0){
		n -= get(n);
		++cnt;
	}
	printf("%lld\n", cnt + n / 2);
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

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

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

li d;

inline bool read() {
	if(!(cin >> d))
		return false;
	return true;
}

inline void solve() {
	if(d == 0) {
		cout << "Y " << 0.0 << " " << 0.0 << endl;
		return;
	}
	if(d < 4) {
		cout << "N" << endl;
		return;
	}
	
	ld D = sqrt(d * li(d - 4));
	ld a = (d + D) / 2.0;
	ld b = (d - D) / 2.0;
	
	cout << "Y " << a << " " << b << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(9);
	
	int tc = 1;
	assert(cin >> tc);
	
	while(tc--) {
		assert(read());
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, pair<int, int> > > g[300043];

int main()
{
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 0; i < m; i++)
	{
		int x, y, w;
		scanf("%d %d %d", &x, &y, &w);
		--x;
		--y;
		g[x].push_back(make_pair(y, make_pair(w, i)));
		g[y].push_back(make_pair(x, make_pair(w, i)));
	}
	set<pair<long long, int> > q;
	vector<long long> d(n, (long long)(1e18));
	d[0] = 0;
	q.insert(make_pair(0, 0));
	vector<int> last(n, -1);
	int cnt = 0;
	vector<int> ans;
	while(!q.empty() && cnt < k)
	{
		auto z = *q.begin();
		q.erase(q.begin());
		int k = z.second;
		if(last[k] != -1)
		{
			cnt++;
			ans.push_back(last[k]);
		}
		for(auto y : g[k])
		{
			int to = y.first;
			int w = y.second.first;
			int idx = y.second.second;
			if(d[to] > d[k] + w)
			{
				q.erase(make_pair(d[to], to));
				d[to] = d[k] + w;
				last[to] = idx;
				q.insert(make_pair(d[to], to));
			}
		}
	}		
	printf("%d\n", ans.size());
	for(auto x : ans) printf("%d ", x + 1);
}	

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 9;

int n, m;	
vector <int> g[N];
vector <pair<int, int> > q[N];
long long add[N];
long long res[N];

void dfs(int v, int pr, int h, long long sum){
	for(auto p : q[v]){
		int l = h, r = h + p.first;
		add[l] += p.second;
		if(r + 1 < N) add[r + 1] -= p.second;
	}
	sum += add[h];
	res[v] = sum;	
	for(auto to : g[v])
		if(to != pr)
			dfs(to, v, h + 1, sum);
			
	for(auto p : q[v]){
		int l = h, r = h + p.first;
		add[l] -= p.second;
		if(r + 1 < N) add[r + 1] += p.second;
	}
}

int main() {	
//	freopen("input.txt", "r", stdin);
	
	scanf("%d", &n);
	for(int i = 0; i < n - 1; ++i){
		int u, v;
		scanf("%d %d", &u, &v);
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	scanf("%d", &m);
	for(int i = 0; i < m; ++i){
		int v, h, d;
		scanf("%d %d %d", &v, &h, &d);
		--v;
		q[v].push_back(make_pair(h, d));
	}
	
	dfs(0, 0, 0, 0);
	for(int i = 0; i < n; ++i)
		printf("%lld ", res[i]);
	puts("");
	
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

typedef long long li;

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

int dp[N][2];

int n, k;
int a[N], b[N];

int get(int pa, int pb, int a, int b){
	int ans = INF;
	
	if (pa <= k){
		int tot = pa + a;
		int cnt = (tot + k - 1) / k - 1;
		if (b == cnt)
			ans = min(ans, tot - cnt * k);
		else if (b > cnt && b <= a * li(k))
			ans = min(ans, 1);
	}
	
	if (pb <= k){
		int cnt = (a + k - 1) / k - 1;
		if (b == cnt)
			ans = min(ans, a - cnt * k);
		else if (b > cnt && b <= (a - 1) * li(k) + (k - pb))
			ans = min(ans, 1);
	}
	
	return ans;
}

int main() {
	scanf("%d%d", &n, &k);
	forn(i, n) scanf("%d", &a[i]);
	forn(i, n) scanf("%d", &b[i]);
	
	forn(i, N) forn(j, 2) dp[i][j] = INF;
	dp[0][0] = 0;
	dp[0][1] = 0;
	forn(i, n){
		dp[i + 1][0] = get(dp[i][0], dp[i][1], a[i], b[i]);
		dp[i + 1][1] = get(dp[i][1], dp[i][0], b[i], a[i]);
	}
	
	puts(dp[n][0] <= k || dp[n][1] <= k ? "YES" : "NO");
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200043;

typedef long long li;

int n, m;
li a[N];
int q;
int f[N * 4];
vector<int> T[4 * N];
vector<int> T2[4 * N];
int mask;
int cur;

vector<int> combine(const vector<int>& a, const vector<int>& b)
{
	vector<int> c(1 << m);
	for(int i = 0; i < (1 << m); i++)
		c[i] = b[a[i]];
	return c;
}

vector<int> init(li x)
{
	vector<int> ans(1 << m);
	for(int i = 0; i < (1 << m); i++)
	{
		if(i != mask || (x & 1) == 0)
			ans[i] = ((i << 1) & mask) ^ 1;
		else
			ans[i] = ((i << 1) & mask);
	}	
	return ans;
}

void upd(int v)
{
	T[v] = combine(T[v * 2 + 2], T[v * 2 + 1]);
	T2[v] = combine(T2[v * 2 + 2], T2[v * 2 + 1]);
}

void build(int v, int l, int r)
{
	if(l == r - 1)
	{
		T[v] = init(a[l]);
		T2[v] = init(a[l] ^ 1);
		return;
	}
	int m = (l + r) >> 1;
	build(v * 2 + 1, l, m);
	build(v * 2 + 2, m, r);
	upd(v);
}

void push(int v, int l, int r)
{
	if(f[v])
	{
		swap(T[v], T2[v]);
		if(l != r - 1)
		{
			f[v * 2 + 1] ^= 1;
			f[v * 2 + 2] ^= 1;
		}
		f[v] = 0;
	}
}

vector<int> id;

void get(int v, int l, int r, int L, int R)
{
	push(v, l, r);
	if(L >= R)
		return;
	if(l == L && r == R)
	{
		cur = T[v][cur];
	}
	else
	{
		int m = (l + r) >> 1;
		get(v * 2 + 2, m, r, max(L, m), R);
		get(v * 2 + 1, l, m, L, min(R, m));
		upd(v);	
	}
}

void add(int v, int l, int r, int L, int R)
{
	push(v, l, r);
	if(L >= R)
		return;
	if(l == L && r == R)
	{
		f[v] ^= 1;
		push(v, l, r);
		return;
	}
	else
	{
		int m = (l + r) >> 1;
		add(v * 2 + 1, l, m, L, min(R, m));
		add(v * 2 + 2, m, r, max(L, m), R);
		upd(v);
	}
}

int main() 
{ 
	scanf("%d %d %d", &n, &m, &q);
	mask = (1 << m) - 1;
	for(int i = 0; i < (1 << m); i++)
		id.push_back(i);
	for(int i = 0; i < n; i++)
		scanf("%lld", &a[i]);
	build(0, 0, n);
	for(int i = 0; i < q; i++)
	{
		int t, l, r;
		scanf("%d %d %d", &t, &l, &r);
		--l;
		if(t == 1)
		{
			li d;
			scanf("%lld", &d);
			if(d & 1)
				add(0, 0, n, l, r);
		}
		else
		{
			cur = mask;
			get(0, 0, n, l, r);
			
			if((cur & 1) == 1)
				puts("1");
			else
				puts("2");
		}
	}
}

n = int(input())
s = input()
for i in range(n - 1):
	if (s[i] != s[i + 1]):
		print("YES")
		print(s[i], s[i + 1], sep="")
		exit(0)
print("NO")

#include <bits/stdc++.h>

using namespace std;

const int N = int(2e5) + 9;

int n;
int a[N];
int b[N];
bool u[N];

int main() {
//	freopen("input.txt", "r", stdin);
	scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
    	scanf("%d", a + i);
    }
    for(int i = 0; i < n; ++i){
    	scanf("%d", b + i);
    }
	
	int pos = 0;
	for(int i = 0; i < n; ++i){
		int x = b[i];
		if(u[x]){
			printf("0 ");
			continue;
		}
		
		int cnt = 0;
		while(true){
			++cnt;
			u[a[pos]] = true;
			if(a[pos] == x) break;
			++pos;
		} 
		
		++pos;
		printf("%d ", cnt);
	}    
	
	puts("");
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(1e5) + 9;

string s;
int n;
int x, y;

void upd(pair<int, int> &pos, char mv, int d){
	if(mv == 'U')
		pos.second += d;
	if(mv == 'D')
		pos.second -= d;
	if(mv == 'L')
		pos.first -= d;
	if(mv == 'R')
		pos.first += d;
}

bool can(pair<int, int> u, pair<int, int> v, int len){
	int d = abs(u.first - v.first) + abs(u.second - v.second);
	if(d % 2 != len % 2) return false;
	return len >= d;
}

bool ok(int len){
	pair<int, int> pos = make_pair(0, 0);
	for(int i = len; i < n; ++i)
		upd(pos, s[i], 1);

	int l = 0, r = len;
	while(true){
		if(can(pos, make_pair(x, y), len))
			return true;
		
		if(r == n) break;
		upd(pos, s[l++], 1);
		upd(pos, s[r++], -1);		
	}
	
	return false;
}

int main() {
	//freopen("input.txt", "r", stdin);
	
	cin >> n;
	cin >> s;
	cin >> x >> y;
	
	if(!ok(n)){
		puts("-1");
		return 0;
	}
	
	int l = -1, r = n;
	while(r - l > 1){
		int mid = (l + r) / 2;
		if(ok(mid)) r = mid;
		else l = mid;
	}
	
	cout << r << endl;
    return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int N = 200 * 1000 + 13;

typedef long long li;

int n;
int a[N];

void get(li T, li& pr, li& cnt){
	pr = 0, cnt = 0;
	forn(i, n){
		if (T >= a[i]){
			T -= a[i];
			pr += a[i];
			++cnt;
		}
	}
}

int main() {
	li T;
	scanf("%d%lld", &n, &T);
	forn(i, n)
		scanf("%d", &a[i]);
	
	int mn = *min_element(a, a + n);
	li ans = 0;
	while (T >= mn){
		li pr, cnt;
		get(T, pr, cnt);
		ans += cnt * (T / pr);
		T %= pr;
	}
	printf("%lld\n", ans);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef pair<long long, int> pt;

const int N = 20;
const int M = 1 << 10;
const int MOD = 998244353;

int k;
int pw10[N];
int bitCnt[M];

pt dp[N][M][2];

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

int mul(int a, int b) {
	return a * 1ll * b % MOD;
}

int calc(const string &s) {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			dp[i][j][0] = dp[i][j][1] = { 0ll, 0 };
		}
	}
	
	int len = s.size();
	dp[0][0][1] = { 1ll, 0 };
	for (int i = 0; i < len; ++i) {
		int cdig = s[i] - '0';
		for (int mask = 0; mask < M; ++mask) {
			if (dp[i][mask][0].x == 0 && dp[i][mask][1].x == 0) continue;
			for (int dig = (i == 0); dig <= 9; ++dig) {
				int nmask = mask | (1 << dig);
				long long cnt = dp[i][mask][0].x;
				int sum = add(dp[i][mask][0].y, mul(dig, mul(pw10[len - i - 1], cnt % MOD)));
				dp[i + 1][nmask][0].x += cnt;
				dp[i + 1][nmask][0].y = add(dp[i + 1][nmask][0].y, sum);
			}
			
			for (int dig = (i == 0); dig <= cdig; ++dig) {
				int nmask = mask | (1 << dig);
				long long cnt = dp[i][mask][1].x;
				int sum = add(dp[i][mask][1].y, mul(dig, mul(pw10[len - i - 1], cnt % MOD)));
				dp[i + 1][nmask][dig == cdig].x += cnt;
				dp[i + 1][nmask][dig == cdig].y = add(dp[i + 1][nmask][dig == cdig].y, sum);
			}
		}
	}
	
	int ans = 0;
	for (int mask = 0; mask < M; ++mask) {
		if (bitCnt[mask] > k) continue;
		ans = add(ans, dp[len][mask][0].y);
		ans = add(ans, dp[len][mask][1].y);
	}
	return ans;
}

int calc(long long n) {
	int len = to_string(n).size();
	int ans = 0;
	for (int l = 1; l < len; ++l) {
		ans = add(ans, calc(string(l, '9')));
	}
	ans = add(ans, calc(to_string(n)));
	return ans;
}

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

	pw10[0] = 1;
	for (int i = 1; i < N; ++i) {
		pw10[i] = mul(pw10[i - 1], 10);
	}
	for (int i = 0; i < M; ++i) {
		bitCnt[i] = __builtin_popcount(i);
	}
	
	long long l, r;
	cin >> l >> r >> k;
	int ans = add(calc(r), -calc(l - 1));
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define size(a) int((a).size())

typedef pair<int, int> pt;

const int N = 200 * 1000 + 11;

int n;
vector<int> g[N];

int p[N];
int dist[N];

bool bad[N];
int value[N];
pt res[N];
vector<pt> best[N];

void dfs(int v, int par = -1, int d = 0) {
	p[v] = par;
	dist[v] = d;
	for (auto to : g[v]) {
		if (to == par) {
			continue;
		}
		dfs(to, v, d + 1);
	}
}

int getFarthest(int v) {
	dfs(v);
	int res = v;
	for (int i = 0; i < n; ++i) {
		if (bad[i]) {
			continue;
		}
		if (dist[res] < dist[i]) {
			res = i;
		}
	}
	return res;
}

pt get(int v) {
	return { dist[v], value[v] };
}

int getBetter(int v, int u) {
	if (get(v) > get(u)) {
		return v;
	}
	return u;
}

int getBest(int v, int par) {
	int res = v;
	for (auto to : g[v]) {
		if (to == par || bad[to]) {
			continue;
		}
		res = getBetter(res, getBest(to, v));
	}
	return res;
}

pt calc(int v) {
	dfs(v);
	
	vector<int> ch;
	for (auto to : g[v]) {
		if (!bad[to]) {
			ch.push_back(to);
		}
	}
	if (size(ch) == 1) {
		return { v, ch[0] };
	}
	
	vector<int> pref(size(ch));
	vector<int> suf(size(ch));
	vector<int> best(size(ch));
	for (int i = 0; i < size(ch); ++i) {
		int to = ch[i];
		best[i] = pref[i] = suf[i] = getBest(to, v);
	}
	for (int i = 1; i < size(ch); ++i) {
		pref[i] = getBetter(pref[i], pref[i - 1]);
		suf[size(ch) - i - 1] = getBetter(suf[size(ch) - i - 1], suf[size(ch) - i]);
	}
	
	pt ans = { -1, -1 };
	pt res = { 0, 0 };
	for (int i = 0; i < size(ch); ++i) {
		int bst = -1;
		if (i == 0) {
			bst = suf[i + 1];
		} else if (i + 1 == size(ch)) {
			bst = pref[i - 1];
		} else {
			bst = getBetter(pref[i - 1], suf[i + 1]);
		}
		pt curRes = { dist[bst] + dist[best[i]], value[bst] + value[best[i]] };
		if (res < curRes) {
			res = curRes;
			ans = { best[i], bst };
		}
	}
	
	return ans;
}

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

	cin >> n;
	for (int i = 0; i < n - 1; ++i) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	int root = -1;
	for (int i = 0; i < n; ++i) {
		if (size(g[i]) > 2) {
			root = i;
			dfs(i);
			break;
		}
	}
	
	for (int i = 0; i < n; ++i) {
		if (size(g[i]) != 1) {
			continue;
		}
		int v = i;
		while (size(g[v]) < 3) {
			bad[v] = true;
			v = p[v];
		}
		best[v].push_back({dist[i] - dist[v], i});
	}
	
	for (int i = 0; i < n; ++i) {
		if (size(best[i]) >= 2) {
			sort(best[i].rbegin(), best[i].rend());
			value[i] = best[i][0].first + best[i][1].first;
			res[i] = { best[i][0].second, best[i][1].second };
		}
	}
	
	int u = getFarthest(root);
	int v = getFarthest(u);
	vector<int> path;
	while (v != u) {
		path.push_back(v);
		v = p[v];
	}
	path.push_back(u);
	
	pt ans = calc(path[size(path) / 2]);
	
	printf("%d %d\n", res[ans.x].x + 1, res[ans.y].x + 1);
	printf("%d %d\n", res[ans.x].y + 1, res[ans.y].y + 1);
	
	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 x first
#define y second

typedef long long li;
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 N = 200 * 1000 + 555;
const int LOGN = 18;

int n, q;
char s[N];

bool read() {
	if(!(cin >> n >> q))
		return false;
	assert(scanf("%s", s) == 1);
	return true;
}

int c[N], id[N], lcp[N];
int mn[LOGN][N];
int lg2[N];

void buildSuffArray() {
	s[n++] = '$';
	
	for(int l = 1; l < 2 * n; l <<= 1) {
		vector< pair<pt, int> > d;
		fore(i, 0, n)
			d.emplace_back(l == 1 ? pt(s[i], 0) : pt(c[i], c[(i + (l >> 1)) % n]), i);
		stable_sort(d.begin(), d.end());
		
		c[d[0].y] = 0;
		fore(i, 1, n)
			c[d[i].y] = c[d[i - 1].y] + (d[i].x != d[i - 1].x);
		if(c[d.back().y] == n - 1)
			break;
	}
	
	fore(i, 0, n)
		id[c[i]] = i;
		
	int l = 0;
	fore(i, 0, n) {
		if(c[i] == n - 1)
			continue;
		l = max(0, l - 1);
		int j = id[c[i] + 1];
		
		while(i + l < n && j + l < n && s[i + l] == s[j + l])
			l++;
		lcp[c[i]] = l;
	}
	
	n--;
	lg2[0] = lg2[1] = 0;
	fore(i, 2, N) {
		lg2[i] = lg2[i - 1];
		if((1 << (lg2[i] + 1)) <= i)
			lg2[i]++;
	}
	
	fore(i, 0, n)
		mn[0][i] = lcp[i];
	fore(pw, 1, LOGN) fore(i, 0, n) {
		mn[pw][i] = mn[pw - 1][i];
		if(i + (1 << (pw - 1)) < n)
			mn[pw][i] = min(mn[pw][i], mn[pw - 1][i + (1 << (pw - 1))]);
	}
}

int getMin(int l, int r) {
	int ln = lg2[r - l];
	return min(mn[ln][l], mn[ln][r - (1 << ln)]);
}

int getLCP(int i, int j) {
	if(i == j) return n - i;
	i = c[i], j = c[j];
	return getMin(min(i, j), max(i, j));
}

bool cmp(const pt &a, const pt &b) {
	if(a.x == b.x)
		return a.y < b.y;
	int l = getLCP(a.x, b.x);
	return s[a.x + l] < s[b.x + l];
}

void solve() {
	buildSuffArray();
	
	fore(_, 0, q) {
		int k, l;
		assert(scanf("%d%d", &k, &l) == 2);
		vector<int> a(k), b(l);
		fore(i, 0, k)
			assert(scanf("%d", &a[i]) == 1), a[i]--;
		fore(j, 0, l)
			assert(scanf("%d", &b[j]) == 1), b[j]--;
			
		li ans = 0;
		vector<pt> c;
		for(auto v : a)
			c.emplace_back(v, 1);
		for(auto v : b)
			c.emplace_back(v, 0);
		sort(c.begin(), c.end(), cmp);
		
		fore(k, 0, 2) {
			li sum = 0;
			map<int, int> cnt;
			
			fore(i, 0, sz(c)) {
				int id = c[i].x, tp = c[i].y;
				if(tp == 0)
					ans += sum;
				else {
					cnt[n - id]++;
					sum += (n - id);
				}
				if(i + 1 < sz(c)) {
					int len = getLCP(c[i].x, c[i + 1].x);
					while(!cnt.empty()) {
						auto it = --cnt.end();
						if(it->x <= len)
							break;
						
						sum -= it->x * 1ll * it->y;
						cnt[len] += it->y;
						sum += it->y * 1ll * len;
						cnt.erase(it);
					}
				}
			}
			reverse(c.begin(), c.end());
		}
		printf("%lld\n", ans);
	}
}

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;
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
    int s, a, b, c;
    int t;
    cin >> t;
    for(int i = 0; i < t; ++i){
        cin >> s >> a >> b >> c;
        
        s /= c;
        int x = s / a;
        s %= a;
        long long res = x * 1LL * (a + b);
        res += s;
        
        cout << res << endl;
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    long long m;
    cin >> n >> m;
    long long cur = 1;
    long long rem = m;
    while(rem > 0){
        long long d = min(cur, rem);
        rem -= d;
        ++cur;
    }
    assert(rem == 0);
    
    long long res = n;
    if(cur > 1) res = n - cur;
    
    cout << max(0ll, n - m * 2) << ' ' << res << endl;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(2e5) + 9;

int n, k, h;
int need = int(1e9);
int cnt[N];

int main() {
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; ++i){
        int x;
        scanf("%d", &x);
        h = max(h, x);
        need = min(need, x);
        ++cnt[x];
    }
    
    int pos = N - 1;
    int res = 0;
    long long sum = 0;
    int c = 0;
    while(true){
        long long x = sum - c * 1LL * (pos - 1);
        if(x > k){
            ++res;
            h = pos;
            sum = pos * 1LL * c;
        }   
    
        --pos;
        if(pos == need) break;
        c += cnt[pos];
        sum += cnt[pos] * 1LL * pos;
    }
    
    if(h != need) ++res;
    
    cout << res << endl;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef pair<int, int> pt;

const int N = 12;
const int M = 305;
const int INF = 1e9;

int n;
int a[N][N];
pt pos[N * N];
pt dist[M][M];

pt operator +(const pt &a, const pt &b){
    return mp(a.x + b.x, a.y + b.y);
}

int dx[] = {-2, -1, 1, 2,  2,  1, -1, -2};
int dy[] = { 1,  2, 2, 1, -1, -2, -2, -1};

bool in(int x, int y){
    return (0 <= x && x < n && 0 <= y && y < n);
}

int get(int x, int y, int p){
    return x * n * 3 + y * 3 + p;
}

pt dp[N * N][3];

int main() {
    scanf("%d", &n);
    forn(i, n) forn(j, n){
        scanf("%d", &a[i][j]);
        --a[i][j];
        pos[a[i][j]] = mp(i, j);
    }
    
    forn(i, M) forn(j, M) dist[i][j] = mp(INF, INF);
    forn(i, M) dist[i][i] = mp(0, 0);
    
    forn(x, n) forn(y, n){
        forn(i, 8){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (in(nx, ny))
                dist[get(x, y, 0)][get(nx, ny, 0)] = mp(1, 0);
        }
        
        for (int i = -n + 1; i <= n - 1; ++i){
            int nx = x + i;
            int ny = y + i;
            if (in(nx, ny))
                dist[get(x, y, 1)][get(nx, ny, 1)] = mp(1, 0);
            ny = y - i;
            if (in(nx, ny))
                dist[get(x, y, 1)][get(nx, ny, 1)] = mp(1, 0);
        }
        
        forn(i, n){
            int nx = x;
            int ny = i;
            dist[get(x, y, 2)][get(nx, ny, 2)] = mp(1, 0);
            nx = i;
            ny = y;
            dist[get(x, y, 2)][get(nx, ny, 2)] = mp(1, 0);
        }
        
        forn(i, 3) forn(j, 3){
            if (i != j){
                dist[get(x, y, i)][get(x, y, j)] = mp(1, 1);
            }
        }
    }
    
    forn(k, M) forn(i, M) forn(j, M)
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    
    forn(i, N * N) forn(j, 3) dp[i][j] = mp(INF, INF);
    dp[0][0] = dp[0][1] = dp[0][2] = mp(0, 0);
    forn(i, n * n - 1) forn(j, 3) forn(k, 3)
        dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + dist[get(pos[i].x, pos[i].y, j)][get(pos[i + 1].x, pos[i + 1].y, k)]);
    
    pt ans = mp(INF, INF);
    ans = min(ans, dp[n * n - 1][0]);
    ans = min(ans, dp[n * n - 1][1]);
    ans = min(ans, dp[n * n - 1][2]);
    
    printf("%d %d\n", ans.x, ans.y);
    return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int N = 200 * 1000 + 13;
const int MOD = 998244353;

int n, m, A;
int b[N];

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

int mul(int a, int b){
    return (a * 1ll * b) % MOD;
}

int binpow(int a, int b){
    int res = 1;
    while (b){
        if (b & 1)
            res = mul(res, a);
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}

int cnt(int x){
    int base = binpow(A, x);
    return mul(add(mul(base, base), base), (MOD + 1) / 2);
}

int main() {
    scanf("%d%d%d", &n, &m, &A);
    forn(i, m)
        scanf("%d", &b[i]);
    
    int ans = binpow(A, n - b[m - 1] * 2);
    ans = mul(ans, cnt(b[0]));
    forn(i, m - 1)
        ans = mul(ans, cnt(b[i + 1] - b[i]));
    
    printf("%d\n", ans);
    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 x first
#define y second

typedef long long li;
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, v.size()) {
        if(i) out << ", ";
        out << v[i];
    }
    return out << "]";
}

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

const int N = 1000 * 1000 + 555;

int n, k;
vector<int> g[N];

inline bool read() {
    if(!(cin >> n >> k))
        return false;
    fore(i, 1, n) {
        int p; assert(scanf("%d", &p) == 1);
        p--;
        
        g[p].push_back(i);
        g[i].push_back(p);
    }
    return true;
}

int h[N];
pt drev[N];

void calcRev(int v, int p) {
    drev[v] = pt(INF, 0);
    for(int to : g[v]) {
        if(to == p) continue;
        
        h[to] = h[v] + 1;
        calcRev(to, v);
        
        if(drev[to].x <= h[v]) {
            drev[v].x = min(drev[v].x, drev[to].x);
            drev[v].y += drev[to].y;
        }
    }
    
    if(p >= 0 && g[v].size() == 1)
        drev[v] = pt(h[v] - k, 1);
}

int d[N];

void calcAns(int v, int p) {
    d[v] = (p >= 0 && g[v].size() == 1);
    for(int to : g[v]) {
        if(to == p) continue;
        calcAns(to, v);
        
        int tmp = drev[v].y;
        if(drev[to].x <= h[v])
            tmp -= drev[to].y;
        
        d[v] = max(d[v], tmp + d[to]);
    }
}

inline void solve() {
    h[0] = 0;
    calcRev(0, -1);
    calcAns(0, -1);
    cout << d[0] << 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>

using namespace std;

typedef long long li;

const li INF64 = li(1e18);

li add(li x, li y)
{
    return min(x + y, INF64);
}

const int N = 243;

int A1[N][2];
li A2[N][N];
int A3[N][N];
int n, m;
li k;
int z;
int p[N];

void build(const string& s)
{
    z = (int)(s.size());
    p[0] = 0;
    for(int i = 1; i < z; i++)
    {
        int j = p[i - 1];
        while(j > 0 && s[j] != s[i])
            j = p[j - 1];
        if(s[j] == s[i])
            j++;
        p[i] = j;
    }
    for(int i = 0; i <= z; i++)
        for(int j = 0; j < 2; j++)
        {
            if(i < z && s[i] == char('0' + j))
                A1[i][j] = i + 1;
            else if(i == 0)
                A1[i][j] = 0;
            else
                A1[i][j] = A1[p[i - 1]][j];
        }
    for(int i = 0; i <= z; i++)
        for(int j = 0; j < 2; j++)
        {
            A3[i][j] = A1[i][j];
            A2[i][j] = (A3[i][j] == z ? 1 : 0);
        }
    for(int i = 2; i <= n; i++)
        for(int j = 0; j <= z; j++)
        {
            A3[j][i] = A3[A3[j][i - 2]][i - 1];
            A2[j][i] = add(A2[j][i - 2], A2[A3[j][i - 2]][i - 1]);
        }
}

int main()
{
    cin >> n >> k >> m;
    string cur = "";
    for(int i = 0; i < m; i++)
    {
        if(cur != "") build(cur);
        li x = 0;
        if(cur != "" && A3[0][n] == i)
            x = 1;
        if(k == 1 && x == 1)
            break;
        k -= x;
        build(cur + '0');
        li x1 = A2[0][n];
        if(k > x1)
        {
            cur += '1';
            k -= x1;
        }
        else
            cur += '0';
    }
    cout << cur << endl;
    return 0;
}

n, k = map(int, input().split())
print((k + n - 1) // n)

q = int(input())

for i in range(q):
    n, m, k = map(int, input().split())
    if (n < m): n, m = m, n
    if (n % 2 != m % 2):
        k -= 1
        n -= 1
    elif (n % 2 != k % 2):
        k -= 2
        n -= 1
        m -= 1
    print(-1 if k < n else k)

#include <bits/stdc++.h>

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

using namespace std;

long long C[20][20];
long long pw[4];

long long cnk(int n, int k){
    if (k < 0 || k > n) return 0;
    return C[n][k];
}

long long get(int n, int lft){
    long long tot = 0;
    forn(i, lft + 1)
        tot += cnk(n, i) * pw[i];
    return tot;
}

long long calc(long long x){
    string s = to_string(x);
    
    long long res = 0;
    int cur = 3;
    int n = s.size();
    
    forn(i, n){
        if (s[i] == '0') continue;
        res += get(n - i - 1, cur);
        --cur;
        if (cur == -1) break;
        res += get(n - i - 1, cur) * (s[i] - '1');
    }
    
    return res;
}

int main() {
    forn(i, 20){
        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];
    }
    pw[0] = 1, pw[1] = 9, pw[2] = 81, pw[3] = 729;
    int T;
    scanf("%d", &T);
    forn(i, T){
        long long L, R;
        scanf("%lld%lld", &L, &R);
        printf("%lld\n", calc(R + 1) - calc(L));
    }
    return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

vector<long long> res;

void brute(int pos, int cnt, long long cur){
    if (pos == 18){
        res.push_back(cur);
        return;
    }
    
    brute(pos + 1, cnt, cur * 10);
    
    if (cnt < 3)
        for (int i = 1; i <= 9; ++i)
            brute(pos + 1, cnt + 1, cur * 10 + i);
}

int main() {
    brute(0, 0, 0);
    res.push_back(1000000000000000000);
    
    int T;
    scanf("%d", &T);
    forn(i, T){
        long long L, R;
        scanf("%lld%lld", &L, &R);
        printf("%d\n", int(upper_bound(res.begin(), res.end(), R) - lower_bound(res.begin(), res.end(), L)));
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 300 * 1000 + 9;

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

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%d", a + i);
    scanf("%d", &m);
    for(int i = 0; i < m; ++i) scanf("%d", b + i);
    
    long long sum = 0;
    for(int i = 0; i < n; ++i) sum += a[i];
    for(int i = 0; i < m; ++i) sum -= b[i];
    if(sum != 0){
        puts("-1");
        return 0;
    }
    
    int posa = 0, posb = 0;
    int res = 0;
    while(posa < n){
        ++res;
        long long suma = a[posa++], sumb = b[posb++];
                
        while(suma != sumb){
            if(suma < sumb) suma += a[posa++];
            else sumb += b[posb++];
        }
    }
    
    printf("%d\n", res);
    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;

struct seg{
    int x1, y1, x2, y2;
    seg(){};
};

struct line{
    long long A, B, C;
    line(){};
    line(seg a){
        A = a.y1 - a.y2;
        B = a.x2 - a.x1;
        C = -A * a.x1 - B * a.y1;
    };
};

int n;
seg a[N];

int get(seg a){
    int dx = a.x1 - a.x2;
    int dy = a.y1 - a.y2;
    return __gcd(abs(dx), abs(dy)) + 1;
}

long long det(long long a, long long b, long long c, long long d){
    return a * d - b * c;
}

bool in(int x, int l, int r){
    if (l > r) swap(l, r);
    return (l <= x && x <= r);
}

bool inter(seg a, seg b, int& x, int& y){
    line l1(a), l2(b);
    long long dx = det(l1.C, l1.B, l2.C, l2.B);
    long long dy = det(l1.A, l1.C, l2.A, l2.C);
    long long d = det(l1.A, l1.B, l2.A, l2.B);
    if (d == 0)
        return false;
    if (dx % d != 0 || dy % d != 0)
        return false;
    x = -dx / d;
    y = -dy / d;
    if (!in(x, a.x1, a.x2) || !in(y, a.y1, a.y2))
        return false;
    if (!in(x, b.x1, b.x2) || !in(y, b.y1, b.y2))
        return false;
    return true;
}

int main() {
    scanf("%d", &n);
    forn(i, n)
        scanf("%d%d%d%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);
    
    int ans = 0;
    int x, y;
    forn(i, n){
        ans += get(a[i]);
        set<pair<int, int>> pts;
        forn(j, i)
            if (inter(a[i], a[j], x, y))
                pts.insert({x, y});
        ans -= pts.size();
    }
    
    printf("%d\n", ans);
    return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int K = 100;
const int N = 100 * 1000 + 13;
const long long INF64 = 3e18;

int mu[K];

void precalc(){
    static bool prime[K];
    static int lst[K];
    
    memset(prime, false, sizeof(prime));
    forn(i, K) lst[i] = i;
    
    for (int i = 2; i < K; ++i){
        if (lst[i] == i) mu[i] = 1;
        for (int j = 2 * i; j < K; j += i){
            lst[j] = min(lst[j], lst[i]);
            if (lst[j] == lst[i])
                mu[j] = 0;
            else
                mu[j] = -mu[i];
        }
    }
}

int mx[K];

long long binpow(long long a, int b){
    long long res = 1;
    while (b){
        if (b & 1){
            if (res < INF64 / a) res *= a;
            else return INF64;
        }
        if (b > 1){
            if (a < INF64 / a) a *= a;
            else return INF64;
        }
        b >>= 1;
    }
    return res;
}

long long calc(long long n){
    int pw = 63 - __builtin_clzll(n);
    for (int i = 3; i <= pw; ++i){
        if (mu[i] == 0) continue;
        while (binpow(mx[i], i) > n)
            --mx[i];
    }
    
    long long res = n - 1;
    for (int i = 2; i <= pw; ++i)
        res -= mu[i] * (mx[i] - 1);
    
    return res;
}

int get_sqrt(long long n){
    int l = 1, r = 1000000000;
    while (l < r - 1){
        int m = (l + r) / 2;
        if (m * 1ll * m <= n)
            l = m;
        else
            r = m;
    }
    return (r * 1ll * r <= n ? r : l);
}

long long ans[N];

int main() {
    precalc();
    int T;
    scanf("%d", &T);
    vector<pair<long long, int>> q;
    
    forn(i, T){
        long long n;
        scanf("%lld", &n);
        q.push_back({n, i});
    }
    
    sort(q.begin(), q.end(), greater<pair<long long, int>>());
    mx[3] = 1000000;
    mx[4] = 31622;
    mx[5] = 3981;
    for (int i = 6; i < K; ++i)
        mx[i] = 1000;
    
    forn(z, T){
        long long n = q[z].first;
        mx[2] = get_sqrt(n);
        ans[q[z].second] = calc(n);
    }
    
    forn(i, T)
        printf("%lld\n", ans[i]);
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1000043;

vector<int> g[N];
vector<int> gt[N];
vector<int> src;
vector<int> snk;
int reach[20];
int used[N];

void dfs(int x)
{
    if(used[x]) return;
    used[x] = 1;
    for(auto y : g[x]) dfs(y);
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        --y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
    for(int i = 0; i < n; i++)
    {
        if(g[i].empty())
            snk.push_back(i);
        if(gt[i].empty())
            src.push_back(i);
    }
    int cnt = src.size();
    for(int i = 0; i < cnt; i++)
    {
        memset(used, 0, sizeof used);
        dfs(src[i]);
        for(int j = 0; j < cnt; j++)
            if(used[snk[j]])
                reach[i] ^= (1 << j);
    }
    bool ok = true;
    for(int mask = 0; mask < (1 << cnt); mask++)
    {
        int res = 0;
        for(int j = 0; j < cnt; j++)
            if(mask & (1 << j))
                res |= reach[j];
        int cnt1 = __builtin_popcount(mask);
        int cnt2 = __builtin_popcount(res);
        if(cnt2 < cnt1 || (cnt2 == cnt1 && cnt1 != 0 && cnt1 != cnt))
            ok = false;
    }
    if(!ok)
        puts("NO");
    else
        puts("YES");
}

#include <bits/stdc++.h>

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

using namespace std;


int main() {
    int T;
    cin >> T;
    
    int n;
    string s;
    forn(_, T){
        cin >> n >> s;
        bool ok = true;
        forn(i, n){
            int k = abs(s[i] - s[n - i - 1]);
            if (k > 2 || k % 2 == 1){
                ok = false;
                break;
            }
        }
        cout << (ok ? "YES" : "NO") << endl;
    }
    return 0;
}

import sys

lst = sys.stdin.readlines()
n, q = map(int, lst[0].split())

for i in range(q):
    x, y = map(int, lst[i + 1].split())
    cnt = (x - 1) * n + y
    ans = (cnt + 1) // 2
    if ((x + y) % 2 == 1): ans += (n * n + 1) // 2
    sys.stdout.write(str(ans) + '\n')

#include <bits/stdc++.h>

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

typedef long long li;

using namespace std;

const int N = 1000 * 1000 + 13;

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

int main() {
    int T;
    scanf("%d", &T);
    forn(_, T){
        scanf("%d", &n);
        forn(i, n)
            scanf("%d", &a[i]);
        sort(a, a + n);
    
        m = 0;
        forn(i, n - 1){
            if (a[i] == a[i + 1]){
                b[m++] = a[i];
                ++i;
            }
        }
    
        int A = b[0], B = b[1];
        li P2 = (A + B) * li(A + B);
        li S = A * li(B);
    
        forn(i, m - 1){
            li p2 = (b[i] + b[i + 1]) * li(b[i] + b[i + 1]);
            li s = b[i] * li(b[i + 1]);
            if (s * P2 > S * p2){
                A = b[i];
                B = b[i + 1];
                S = s;
                P2 = p2;
            }
        }
    
        printf("%d %d %d %d\n", A, A, B, B);
    }
}

#include<bits/stdc++.h>

using namespace std;

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

#define mp make_pair
#define pb push_back

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

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<li, li> 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 << "[";
    forn(i, sz(v)) {
        if(i) out << ", ";
        out << v[i];
    }
    return out << "]";
}

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

int n;
vector<int> a, c;

inline bool read() {
    if(!(cin >> n))
        return false;
    c.assign(n, 0);
    a.assign(n, 0);

    forn(i, n)
        assert(scanf("%d", &c[i]) == 1);
    forn(i, n) {
        assert(scanf("%d", &a[i]) == 1);
        a[i]--;
    }
    return true;
}

vector< vector<int> > cycles;

vector<char> used;
vector<int> path;

void dfs(int v) {
    path.push_back(v);
    used[v] = 1;

    int to = a[v];
    if(used[to] != 2) {
        if(used[to] == 1) {
            cycles.emplace_back();

            int id = sz(path) - 1;
            while(path[id] != to)
                cycles.back().push_back(path[id--]);
            cycles.back().push_back(to);
        } else
            dfs(to);
    }
    path.pop_back();
    used[v] = 2;
}

inline void solve() {
    used.assign(n, 0);

    forn(i, n) {
        if (!used[i])
            dfs(i);
    }

    li ans = 0;
    for(auto &cur : cycles) {
        int mn = c[cur[0]];
        for(int v : cur)
            mn = min(mn, c[v]);
        ans += mn;
    }
    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;

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

int n, k;
int dp[2][N][N];
int cnt[N];
int pr[N];

void add(int &a, int b){
    a += b;
    if (a >= MOD)
        a -= MOD;
}

int main() {
    scanf("%d%d", &n, &k);
    
    dp[0][0][0] = 1;
    forn(ii, n){
        int i = ii & 1;
        int ni = i ^ 1;
        memset(dp[ni], 0, sizeof(dp[ni]));
        forn(j, n + 1){
            forn(k, n + 1){
                add(dp[ni][j + 1][max(j + 1, k)], dp[i][j][k]);
                add(dp[ni][1][max(1, k)], dp[i][j][k]);
            }
        }
    }
    
    forn(i, n + 1)
        forn(j, n + 1)
            add(cnt[i], dp[n & 1][j][i]);
    
    forn(i, n + 1){
        add(pr[i + 1], pr[i]);
        add(pr[i + 1], cnt[i]);
    }
    
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        add(ans, cnt[i] * (long long)(pr[min(n + 1, (k - 1) / i + 1)]) % MOD);
    
    ans = (ans * (long long)((MOD + 1) / 2)) % MOD;
    printf("%d\n", ans);
    
    return 0;
}

def norm(x):
    return (x % 998244353 + 998244353) % 998244353

n, k = map(int, input().split())

dp1 = [0]
dp2 = [0]

for i in range(n):
    l = [1]
    cur = 0
    for j in range(n + 1):
        cur += l[j]
        if(j > i):
            cur -= l[j - i - 1]
        cur = norm(cur)
        l.append(cur)
    dp1.append(l[n])
    dp2.append(norm(dp1[i + 1] - dp1[i]))

ans = 0
for i in range(n + 1):
    for j in range(n + 1):
        if(i * j < k):
            ans = norm(ans + dp2[i] * dp2[j])

ans = norm(ans * 2)

print(ans)

#include <bits/stdc++.h>

using namespace std;

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

const int N = 2 * 1000 * 1000 + 11;
const int INF = 1e9 + 1;

int n;
int a[N][2];
vector<int> s;
bool used[N];
bool exam[N];
vector<pair<int, int>> g[N];

bool deny(int v) {
    if (used[v]) return false;
    used[v] = true;
    for (auto it : g[v]) {
        int to = it.first;
        int ex = it.second;
        if (exam[ex]) continue;
        if (used[to])
            return false;
        exam[ex] = true;
        if (!deny(to))
            return false;
    }
    return true;
}

int cntv, cnte;

void dfs(int v) {
    ++cntv;
    used[v] = true;
    for (auto it : g[v]) {
        int to = it.first;
        int ex = it.second;
        if (exam[ex]) continue;
        exam[ex] = true;
        ++cnte;
        if (!used[to])
            dfs(to);
    }
}

bool check(int day) {
    memset(used, false, sizeof(used));
    memset(exam, false, sizeof(exam));
    forn(i, s.size()) if (i > day) {
        if (!deny(i)) {
            return false;
        }
    }
    
    forn(i, s.size()) {
        if (!used[i]) {
            cntv = 0;
            cnte = 0;
            dfs(i);
            if (cntv < cnte)
                return false;
        }
    }
    
    return true;
}

int main() {
    scanf("%d", &n);
    forn(i, n) forn(j, 2) {
        scanf("%d", &a[i][j]);
        s.push_back(a[i][j]);
    }
    
    sort(s.begin(), s.end());
    s.resize(unique(s.begin(), s.end()) - s.begin());
    
    forn(i, n) {
        forn(j, 2) {
            a[i][j] = lower_bound(s.begin(), s.end(), a[i][j]) - s.begin();
        }
        g[a[i][0]].push_back(make_pair(a[i][1], i));
        g[a[i][1]].push_back(make_pair(a[i][0], i));
    }
        
    int l = 0, r = int(s.size()) - 1;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
    for (int i = l; i <= r; ++i) {
        if (check(i)) {
            printf("%d\n", s[i]);
            return 0;
        }
    }
    puts("-1");
}

#include <bits/stdc++.h>

using namespace std;

mt19937 rnd(time(NULL));

const int N = 2 * 1000 * 1000 + 11;
const int INF = 1e9;

int n;
int a[N][2];

vector<int> nums;
int m;

vector<int> g[N];
int mt[N];
int used[N];
int T = 1;

bool try_kuhn(int v) {
    if (used[v] == T)
        return false;
    used[v] = T;
    
    for (auto to : g[v]) {
        if (mt[to] == -1) {
            mt[to] = v;
            return true;
        }
    }
    
    for (auto to : g[v]) {
        if (try_kuhn(mt[to])) {
            mt[to] = v;
            return true;
        }
    }
    
    return false;
}

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

    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 2; ++j) {
            scanf("%d", &a[i][j]);
            nums.push_back(a[i][j]);
        }
    }
    
    sort(nums.begin(), nums.end());
    nums.resize(unique(nums.begin(), nums.end()) - nums.begin());
    m = nums.size();
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 2; ++j) {
            a[i][j] = lower_bound(nums.begin(), nums.end(), a[i][j]) - nums.begin();
        }
    }
    
    for (int i = 0; i < n; ++i) {
        g[a[i][0]].push_back(i);
        g[a[i][1]].push_back(i);
    }

    memset(mt, -1, sizeof(mt)); 
    int match = 0;
    for (int i = 0; i < m; ++i) {
        if (try_kuhn(i)) {
            ++T;
            ++match;
            if (match == n) {
                printf("%d\n", nums[i]);
                return 0;
            }
        }
    }
    
    puts("-1");
    
    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 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 ld EPS = 1e-9;

li m, x;

inline bool read() {
    if(!(cin >> m >> x))
        return false;
    return true;
}

map< li, vector<pt> > dFact;
vector<pt> fact(li v) {
    if(dFact.count(v))
        return dFact[v];
    
    li oldv = v;
    vector<pt> fs;
    for(li d = 2; d * d <= v; d++) {
        int cnt = 0;
        while(v % d == 0)
            v /= d, cnt++;
        
        if(cnt > 0)
            fs.emplace_back(d, cnt);
    }
    if(v > 1)
        fs.emplace_back(v, 1), v = 1;
    return dFact[oldv] = fs;
}

vector<pt> merge(const vector<pt> &a, const vector<pt> &b) {
    vector<pt> ans;
    int u = 0, v = 0;
    while(u < sz(a) && v < sz(b)) {
        if(a[u].x < b[v].x)
            ans.push_back(a[u++]);
        else if(a[u].x > b[v].x)
            ans.push_back(b[v++]);
        else {
            ans.emplace_back(a[u].x, a[u].y + b[v].y);
            u++, v++;
        }
    }
    while(u < sz(a))
        ans.push_back(a[u++]);
    while(v < sz(b))
        ans.push_back(b[v++]);
    return ans;
}

li getPw(li a, li b) {
    li ans = 1;
    fore(i, 0, b)
        ans *= a;
    return ans;
}

li mul(li a, li b, li mod) {
    li m = li(ld(a) * b / mod);
    li rem = a * b - m * mod;
    while(rem < 0)
        rem += mod;
    while(rem >= mod)
        rem -= mod;
    return rem;
}

li binPow(li a, li k, li mod) {
    li ans = 1 % mod;
    while(k > 0) {
        if(k & 1)
            ans = mul(ans, a, mod);
        a = mul(a, a, mod);
        k >>= 1;
    }
    return ans;
}

li findOrder(li x, li mod, const vector<pt> &f) {
    li phi = 1;
    fore(i, 0, sz(f)) fore(k, 0, f[i].y)
        phi *= f[i].x;
        
    if(phi == 1 || x == 0)
        return 1;
    
    li ord = 1;
    fore(i, 0, sz(f)) {
        li basePw = phi;
        fore(k, 0, f[i].y)
            basePw /= f[i].x;
        
        li curV = binPow(x, basePw, mod);
        
        int curPw = -1;
        fore(k, 0, f[i].y + 1) {
            if(curV != 1)
                curPw = k;
            curV = binPow(curV, f[i].x, mod);
        }
        
        ord *= getPw(f[i].x, curPw + 1);
    }
    return ord;
}

vector<pt> fm;
vector<int> pw;

li calc(int pos, li dv) {
    if(pos >= sz(fm)) {
        vector<pt> cf = fm;
        fore(i, 0, sz(fm))
            cf[i].y = max(pw[i] - 1, 0);
        
        li phi = dv;
        fore(i, 0, sz(fm)) {
            if(pw[i] > 0) {
                cf = merge(cf, fact(fm[i].x - 1));
                phi -= phi / fm[i].x;
            }
        }
        li k = findOrder(x % dv, dv, cf);
        return phi / k;
    }
    
    li ans = 0;
    fore(i, 0, fm[pos].y + 1) {
        pw[pos] = i;
        ans += calc(pos + 1, dv);
        dv *= fm[pos].x;
    }
    return ans;
}

inline void solve() {
    fm = fact(m);
    
    pw.assign(sz(fm), 0);
    li ans = calc(0, 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;
}

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
pos = 0
for i in a:
	pos += (pos < len(b) and b[pos] >= i)
print(pos)

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	string s;
	cin >> s;
	
	string ans;
	
	int cnt = 0;
	for (auto c : s) {
		if (c == '1') ++cnt;
		else ans += c;
	}
	
	int n = ans.size();
	int pos = -1;
	while (pos + 1 < n && ans[pos + 1] == '0') ++pos;
	ans.insert(pos + 1, string(cnt, '1'));
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

typedef long long li;

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	
	li neg = ((n - 1) / 2) * li((n - 1) / 2 + 1);
	if (n % 2 == 0) neg += n / 2;
	li pos = n * li(n - 1) / 2;
	
	li ans = 0;
	forn(i, m){
		int x, d;
		scanf("%d%d", &x, &d);
		ans += x * li(n);
		if (d < 0)
			ans += neg * d;
		else
			ans += pos * d;
	}
	
	printf("%.15f\n", double(ans) / 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 = 100000;

pair<int, int> ans[N];

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	
	if (m < n - 1) {
		puts("Impossible");
		return 0;
	}
	
	int cur = 0;
	
	forn(i, n) for (int j = i + 1; j < n; ++j){
		if (cur == m)
			break;
		if (__gcd(i + 1, j + 1) == 1)
			ans[cur++] = make_pair(j, i);
	}
	
	if (cur != m){
		puts("Impossible");
		return 0;
	}
	
	puts("Possible");
	forn(i, m)
		printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int add(int x, int y)
{
    x += y;
    while(x >= MOD)
        x -= MOD;
    while(x < 0)
        x += MOD;
    return x;
}

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

int main()
{
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
        
    int ans = 0;
    vector<int> pw2(1, 1);
    while(pw2.size() < n)
        pw2.push_back(mul(pw2.back(), 2));
    int cur = mul(pw2[n - 1], a[0]);
    for(int i = 0; i < n; i++)
    {
        ans = add(ans, cur);
        if(i < n - 1)
        {
            cur = add(cur, -mul(pw2[n - 2 - i], a[i]));
            cur = add(cur, mul(pw2[n - 2 - i], a[i + 1]));
        }
    }
    printf("%d\n", ans);
}

#define _CRT_SECURE_NO_WARNINGS

#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>

// RJ? No, thanks

using namespace std;

const int N = 1000043;

struct state
{
	vector<int>* a;
	int cur_max;
	int sz()
	{
		return a->size();
	}
	void add(int i, int val)
	{
		(*a)[i] += val;
		if(make_pair((*a)[i], i) > make_pair((*a)[cur_max], cur_max))
			cur_max = i;
	}
};

state pull(state z)
{
	if(z.sz() == 0)
	{
		state c;
		c.a = new vector<int>(1, 1);
		c.cur_max = 0;
		return c;
	}
	else
	{
		state c;
		c.a = z.a;
		c.cur_max = z.cur_max;
		c.a->push_back(0);
		c.add(c.sz() - 1, 1);
		return c;
	}
}

state merge(state a, state b)
{
	if(a.sz() < b.sz())
		swap(a, b);
	state c;
	c.a = a.a;
	c.cur_max = a.cur_max;
	int as = c.sz();
	int bs = b.sz();
	for(int i = 0; i < bs; i++)
		a.add(as - i - 1, (*(b.a))[bs - i - 1]);
	return a;
}

state s[N];
int ans[N];
vector<int> g[N];

void dfs(int x, int p = -1)
{
	s[x].a = new vector<int>(0);
	s[x].cur_max = 0;
	for(auto y : g[x])
		if(y != p)
		{
			dfs(y, x);
			s[x] = merge(s[x], s[y]);
		}
	s[x] = pull(s[x]);
	ans[x] = s[x].sz() - s[x].cur_max - 1;
}

int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n - 1; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		--x;
		--y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(0);
	for(int i = 0; i < n; i++)
		printf("%d\n", ans[i]);
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

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

struct edge
{
    int y;
    int c;
    int f;
    edge() {};
    edge(int y, int c, int f) : y(y), c(c), f(f) {};
};

const int N = 100;

vector<edge> e;
vector<int> g[N];
int edge_num[N][N];
int char_vertex[6];
int mask_vertex[N];
int used[N];
int cc = 0;
int s, t;

void add_edge(int x, int y, int c)
{
    edge_num[x][y] = sz(e);
    g[x].push_back(sz(e));
    e.push_back(edge(y, c, 0));
    edge_num[y][x] = sz(e);
    g[y].push_back(sz(e));
    e.push_back(edge(x, 0, 0));
}

int rem(int num)
{
    return e[num].c - e[num].f;
}

int dfs(int x, int mx)
{
    if(x == t) return mx;
    if(used[x] == cc) return 0;
    used[x] = cc;
    for(auto num : g[x])
    {
        if(rem(num))
        {
            int pushed = dfs(e[num].y, min(mx, rem(num)));
            if(pushed)
            {
                e[num].f += pushed;
                e[num ^ 1].f -= pushed;
                return pushed;
            }
        }
    }
    return 0;
}

bool check(int ch, int mask)
{
    if((mask & (1 << ch)) == 0)
        return false;
    int cv = char_vertex[ch];
    int mv = mask_vertex[mask];
    int e1 = edge_num[s][cv];
    int e2 = edge_num[mv][t];
    if(e[e1].f == 0 || e[e2].f == 0)
        return false;
    e[e1].f--;
    e[e1 ^ 1].f++;
    vector<int> affected_edges;
    affected_edges.push_back(e1);
    for(auto x : g[cv])
    {
        if((x & 1) == 0 && e[x].f > 0)
        {
            affected_edges.push_back(x);
            e[x].f--;
            e[x ^ 1].f++;
            int y = e[x].y;
            for(auto x2 : g[y])
            {
                if((x2 & 1) == 0)
                {
                    affected_edges.push_back(x2);
                    e[x2].f--;
                    e[x2 ^ 1].f++;
                    break;
                }
            }
            break;
        }
    }
    if(e[e2].f < e[e2].c)
    {
        e[e1].c--;
        e[e2].c--;
        return true;
    }
    affected_edges.push_back(e2);
    e[e2].f--;
    e[e2 ^ 1].f++;
    for(auto x : g[mv])
    {
        if((x & 1) == 1 && e[x].f < 0)
        {
            affected_edges.push_back(x ^ 1);
            e[x].f++;
            e[x ^ 1].f--;
            int y = e[x].y;
            for(auto x2 : g[y])
            {
                if((x2 & 1) == 1)
                {
                    affected_edges.push_back(x2 ^ 1);
                    e[x2].f++;
                    e[x2 ^ 1].f--;
                    break;
                }
            }
            break;
        }
    }
    cc++;
    e[e1].c--;
    e[e2].c--;
    if(dfs(s, 1))
        return true;
    else
    {
        e[e1].c++;
        e[e2].c++;
        for(auto x : affected_edges)
        {
            e[x].f++;
            e[x ^ 1].f--;
        }
        return false;
    }
}

char buf[100043];
string allowed[100043];
int allowed_mask[100043];

int main()
{
    s = 70;
    t = 71;
    scanf("%s", buf);
    string z = buf;
    int n = sz(z);
    int m;
    scanf("%d", &m);
    for(int i = 0; i < n; i++)
    {
        allowed[i] = "abcdef";
        allowed_mask[i] = 63;
    }
    for(int i = 0; i < m; i++)
    {
        int idx;
        scanf("%d", &idx);
        --idx;
        scanf("%s", buf);
        allowed[idx] = buf;
        allowed_mask[idx] = 0;
        for(auto x : allowed[idx])
        {
            allowed_mask[idx] |= (1 << (x - 'a'));
        }
    }
    for(int i = 0; i < 6; i++)
        char_vertex[i] = i;
    for(int i = 0; i < (1 << 6); i++)
        mask_vertex[i] = i + 6;
    for(int i = 0; i < (1 << 6); i++)
        for(int j = 0; j < 6; j++)
            if(i & (1 << j))
                add_edge(char_vertex[j], mask_vertex[i], 100000);
    for(int i = 0; i < 6; i++)
    {
        int cnt = 0;
        for(int j = 0; j < n; j++)
            if(z[j] == 'a' + i)
                cnt++;
        add_edge(s, char_vertex[i], cnt);
    }
    for(int i = 0; i < (1 << 6); i++)
    {
        int cnt = 0;
        for(int j = 0; j < n; j++)
            if(allowed_mask[j] == i)
                cnt++;
        add_edge(mask_vertex[i], t, cnt);
    }
    int flow = 0;
    while(true)
    {
        cc++;
        int p = dfs(s, 100000);
        if(p)
            flow += p;
        else
            break;
    }
    if(flow != n)
    {
        puts("Impossible");
        return 0;
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < 6; j++)
        {
            if(check(j, allowed_mask[i]))
            {
                printf("%c", j + 'a');
                break;
            }
        }
    puts("");
}

#include <bits/stdc++.h>

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

int main() {
	long long n, m;
	int a, b;
	
	cin >> n >> m >> a >> b;
	cout << min(n % m * b, (m - n % m) * a) << endl;
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 200 * 1000 + 555;
int n, k, a[N];

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

inline void solve() {
	sort(a, a + n);
	a[n++] = int(2e9);
	
	int ans = 0, u = 0;
	for(int i = 0; i < n - 1; i++) {
		while(u < n && a[i] == a[u])
			u++;
		if(a[u] - a[i] > k)
			ans++;
	}
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif

	if(read()) {
		solve();
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 7;

int n;
string s[N];
char buf[N];
int cnt[N];

int getBalance(string &s){
	int bal = 0;
	for(int i = 0; i < s.size(); ++i){
		if(s[i] == '(')
			++bal;
		else
			--bal;
		
		if(bal < 0)
			return -1;
	}
	
	return bal;
}

string rev(string &s){
	string revs = s;
	reverse(revs.begin(), revs.end());
	for(int i = 0; i < revs.size(); ++i)
		if(revs[i] == '(')
			revs[i] = ')';
		else
			revs[i] = '(';
		
	return revs;
}

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; ++i){
		scanf("%s", buf);
		s[i] = buf;
	}

	for(int i = 0; i < n; ++i){
		int bal = getBalance(s[i]);
		if(bal != -1)
			++cnt[bal];
	}
	
	long long res = 0;	
	for(int i = 0; i < n; ++i){
		s[i] = rev(s[i]);
		int bal = getBalance(s[i]);
		if(bal != -1)
			res += cnt[bal];
	}
	
	printf("%I64d\n", res);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(1e3) + 7;

int n, a, b;
bool mat[N][N];

int main(){
	scanf("%d %d %d", &n, &a, &b);

	if(min(a, b) > 1){
		puts("NO");
		return 0;
	}
	
	if(a == 1 && b == 1){
		if(n == 2 || n == 3){
			puts("NO");
			return 0;
		}
		puts("YES");
		for(int i = 1; i < n; ++i)
			mat[i][i - 1] = mat[i - 1][i] = true;
		for(int i = 0; i < n; ++i){
			for(int j = 0; j < n; ++j)
				printf("%c", '0' + mat[i][j]);
			puts("");
		}
		return 0;
	}
	
	bool x = false;
	if(a == 1){
		swap(a, b);
		x = true;
	}
	for(int i = n - a; i > 0; --i)
		mat[i][i - 1] = mat[i - 1][i] = true;
	puts("YES");
	for(int i = 0; i < n; ++i){
			for(int j = 0; j < n; ++j)
				printf("%c", '0' + ((x ^ mat[i][j]) && (i != j)));
			puts("");
		}
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int INF = 1e9;
const long long INF64 = 1e18;
const int N = 1000 * 1000 + 13;

int n, m, k;
bool pos[N];
int lst[N], s[N], a[N];

int get(int l){
	int r = 0, i = -1, res = 0;
	while (r < n){
		if (lst[r] <= i)
			return INF;
		i = lst[r];
		r = lst[r] + l;
		++res;
	}
	return res;
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	forn(i, m) scanf("%d", &s[i]);
	forn(i, k) scanf("%d", &a[i]);
	forn(i, n) pos[i] = true;
	forn(i, m) pos[s[i]] = false;
	forn(i, n){
		if (pos[i])
			lst[i] = i;
		else if (i)
			lst[i] = lst[i - 1];
		else
			lst[i] = -1;
	}
	long long ans = INF64;
	forn(i, k){
		long long t = get(i + 1);
		if (t != INF)
			ans = min(ans, a[i] * t);
	}
	printf("%lld\n", ans == INF64 ? -1 : ans);
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

mt19937 rnd(time(NULL));

const int N = 1'000'013;

int n, m;
pair<int, int> e[N];
int a[N], rk[N];
long long sum[N], ans[N];

int p[N];

int getP(int a){
	return (a == p[a] ? a : p[a] = getP(p[a]));
}

bool merge(int a, int b){
	a = getP(a);
	b = getP(b);
	if (a == b) return false;
	if (rk[a] > rk[b]) swap(a, b);
	p[a] = b;
	rk[b] += rk[a];
	return true;
}

bool used[N];
vector<int> g[N];
int h[N];

void dfs(int v, int p){
	sum[v] = a[v];
	for (auto u : g[v]){
		if (u != p){
			h[u] = h[v] + 1;
			dfs(u, v);
			sum[v] += sum[u];
		}
	}
}

int main() {
	scanf("%d", &n);
	forn(i, n)
		scanf("%d", &a[i]);
	
	forn(i, n) p[i] = i, rk[i] = 1;
	scanf("%d", &m);
	forn(i, m){
		int &v = e[i].first;
		int &u = e[i].second;
		scanf("%d%d", &v, &u);
		--v, --u;
		if (merge(v, u)){
			g[v].push_back(u);
			g[u].push_back(v);
			used[i] = true;
		}
	}
	
	long long tot = 0;
	forn(i, n) tot += a[i];
	if (tot != 0){
		puts("Impossible");
		return 0;
	}
	
	dfs(0, -1);
	
	puts("Possible");
	forn(i, m){
		if (used[i]){
			int v = e[i].first, u = e[i].second;
			if (h[v] < h[u])
				ans[i] = sum[u];
			else
				ans[i] = -sum[v];
		}
		printf("%lld\n", ans[i]);
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;

int d[N];

void sieve()
{
	vector<int> pr;
 	for(int i = 2; i < N; i++) 
 	{
		if (d[i] == 0) 
		{
			d[i] = i;
			pr.push_back(i);
		}
		for(auto x : pr)
		{
			if (x > d[i] || x * 1ll * i >= N)
				break;
			d[i * x] = x;
		}
	}
}

int mobius(int x)
{
	int last = -1;
	int res = 1;
	while(x != 1)
	{
		if(last == d[x])
			res = 0;
		else
			res = -res;
		last = d[x];
		x /= d[x];
	}
	return res;
}

int mb[N];

vector<int> need_bfs[N];
int used[N];
vector<int> g[N];
int a[N];
int cc = 0;
int q[N];
int hd, tl;
int good[N];

int bfs(int x, int gc)
{
    hd = 0;
    tl = 0;
    q[tl++] = x;
    used[x] = cc;
    while(hd < tl)
    {
        int z = q[hd++];
        for(auto y : g[z])
        {
            if(good[a[y]] == cc && used[y] < cc)
            {
                used[y] = cc;
                q[tl++] = y;
            }
        }
    }
	return tl;
}

long long ans1[N];
long long ans2[N];

int main() {
	sieve();
	for(int i = 1; i < N; i++)
		mb[i] = mobius(i);
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	for(int i = 0; i < n - 1; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		--x;
		--y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i = 0; i < n; i++)
	{
		need_bfs[a[i]].push_back(i);
	}
	for(int i = 200000; i >= 1; i--)
	{
		cc++;
		for(int j = i; j <= 200000; j += i)
		    good[j] = cc;
		for(int j = i; j <= 200000; j += i)
		    for(auto x : need_bfs[j])
		    {
		        if(used[x] == cc) continue;
			    int z = bfs(x, i);
			    ans1[i] += z * 1ll * (z + 1) / 2;
		    }
	    for(int j = i, k = 1; j <= 200000; j += i, k++)
	        ans2[i] += mb[k] * ans1[j];
	}
	for(int i = 1; i <= 200000; i++)
		if(ans2[i])
			printf("%d %lld\n", i, ans2[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 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 << "[";
	for(auto &e : v)
		out << e << ", ";
	return out << "]";
}

const int N = 1000 * 1000 + 555;
const int LOGN = 21;
int mind[N];
int pw[LOGN][N];

int n, a[N];
vector<int> g[N];
li res[N];

bool gen() {
	mt19937 rnd(42);
	n = 200 * 1000;
	fore(i, 0, n)
		a[i] = 831600;
	fore(i, 1, n) {
		int u = rnd() % i, v = i;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	return true;
}

inline bool read() {
//	return gen();
	if(!(cin >> n))
		return false;
	fore(i, 0, n)
		assert(scanf("%d", &a[i]) == 1);
	fore(i, 0, n - 1) {
		int u, v;
		assert(scanf("%d%d", &u, &v) == 2);
		u--, v--;
		
		g[u].push_back(v);
		g[v].push_back(u);
	}
	return true;
}

vector<pt> dv[N];

inline int gcd(int a, int b) {
	int ans = 1;
	unsigned int u = 0, v = 0;
	while(u < dv[a].size() && v < dv[b].size()) {
		if(dv[a][u].x < dv[b][v].x)
			u++;
		else if(dv[a][u].x > dv[b][v].x)
			v++;
		else {
			ans *= pw[min(dv[a][u].y, dv[b][v].y)][dv[a][u].x];
			u++, v++;
		}
	}
	return ans;
}

bool used[N];
int sz[N];

void calcSz(int v, int p) {
	sz[v] = 1;
	for(int to : g[v]) {
		if(to == p || used[to])
			continue;
		calcSz(to, v);
		sz[v] += sz[to];
	}
}

int findC(int v, int p, int all) {
	for(int to : g[v]) {
		if(to == p || used[to])
			continue;
		if(sz[to] > all / 2)
			return findC(to, v, all);
	}
	return v;
}

int u[N], T = 0;
int cntD[N];

inline void addDiv(int d, int cnt) {
	if(u[d] != T)
		u[d] = T, cntD[d] = 0;
	cntD[d] += cnt;
}

int cds[N], szcds;

void calcDs(int v, int p, int gc) {
	gc = gcd(a[v], gc);
	cds[szcds++] = gc;
	for(int to : g[v]) {
		if(to == p || used[to])
			continue;
		calcDs(to, v, gc);
	}
}

vector<int> cps, cmx, vmx;

void check(int curd, int curg, int pos, int add) {
	if(pos >= (int)cps.size()) {
		if(u[curd] == T)
			res[curg] += cntD[curd] * 1ll * add;
		return;
	}
	
	fore(st, 0, cmx[pos] + 1) {
		check(curd, curg, pos + 1, add);
		
		curd *= cps[pos];
		if(st < vmx[pos])
			curg *= cps[pos];
	}
}

pt ops[N]; int szops;
int cntDiff[N];

void calc(int v) {
	calcSz(v, -1);
	int c = findC(v, -1, sz[v]);
	used[c] = 1;
	
//	cerr << "C = "<< c << endl;
	
	cps.resize(dv[a[c]].size());
	cmx.resize(cps.size());
	vmx.resize(cmx.size());
	
	fore(i, 0, cps.size()) {
		cps[i] = dv[a[c]][i].x;
		cmx[i] = dv[a[c]][i].y;
	}
	
	T++;
	addDiv(a[c], 1);
	
	for(int to : g[c]) {
		if(used[to]) continue;
		
		szcds = 0;
		calcDs(to, c, a[c]);
		fore(i, 0, szcds)
			cntDiff[cds[i]]++;
			
		szops = 0;
		fore(j, 0, szcds) {
			if(cntDiff[cds[j]] == 0)
				continue;
			
			int p = 0, val = cds[j];
			fore(i, 0, vmx.size()) {
				if(p >= (int)dv[val].size() || dv[val][p].x > cps[i])
					vmx[i] = 0;
				else
					vmx[i] = dv[val][p].y, p++;
			}
			
			check(1, 1, 0, cntDiff[cds[j]]);
			ops[szops++] = {cds[j], cntDiff[cds[j]]};
			cntDiff[cds[j]] = 0;
		}
		
		fore(j, 0, szops)
			addDiv(ops[j].x, ops[j].y);
	}
	
	for(int to : g[c]) {
		if(used[to]) continue;
		calc(to);
	}
}

inline void solve() {
	iota(mind, mind + N, 0);
	fore(i, 2, N) {
		if(mind[i] != i)
			continue;
		
		pw[0][i] = 1;
		fore(st, 1, LOGN)
			pw[st][i] = pw[st - 1][i] * i;
		
		for(li j = i * 1ll * i; j < N; j += i)
			mind[j] = min(mind[j], i);
	}
	fore(i, 2, N) {
		int val = i;
		while(mind[val] > 1) {
			if(dv[i].empty() || dv[i].back().x != mind[val])
				dv[i].emplace_back(mind[val], 0);
			dv[i].back().y++;
			val /= mind[val];
		}
	}
	
	memset(res, 0, sizeof res);
	
	T = 0;
	calc(0);
	
	fore(i, 0, n)
		res[a[i]]++;
	
	fore(i, 1, 1000'000 + 1) {
		if(res[i])
			printf("%d %lld\n", i, res[i]);
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif

	if(read()) {
		solve();
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> pos(n / 2);
	for (int i = 0; i < n / 2; ++i)
		cin >> pos[i];
	sort(pos.begin(), pos.end());
	
	int ans1 = 0, ans2 = 0;
	for (int i = 0; i < n / 2; ++i) {
		ans1 += abs(pos[i] - (i * 2 + 1));
		ans2 += abs(pos[i] - (i * 2 + 2));
	}
	
	cout << min(ans1, ans2) << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<string> s(n);
	vector<int> cnt(m);
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
		for (int j = 0; j < m; ++j)
			if (s[i][j] == '1') ++cnt[j];
	}
	
	for (int i = 0; i < n; ++i) {
		bool ok = true;
		for (int j = 0; j < m; ++j) {
			if (s[i][j] == '1' && cnt[j] == 1)
				ok = false;
		}
		if (ok) {
			puts("YES");
			return 0;
		}
	}
	
	puts("NO");
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

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

typedef long long li;

int n, k, l, m;
vector<li> a;

inline bool read() {
	if(!(cin >> n >> k >> l))
		return false;
	m = n * k;
	a.assign(m, 0);
	fore(i, 0, m)
		assert(scanf("%lld", &a[i]) == 1);
	return true;
}

inline void solve() {
	sort(a.begin(), a.end());
	int rg = int(upper_bound(a.begin(), a.end(), a[0] + l) - a.begin());
	
	if(rg < n) {
		puts("0");
		return;
	}
	li ans = 0;
	
	int u = 0;
	fore(i, 0, n) {
		ans += a[u++];
		
		fore(j, 0, k - 1) {
			if(rg - u > n - i - 1)
				u++;
			else
				break;
		}
	}
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cerr << 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++)

typedef long long li;

using namespace std;

const int INF = 2e9;
li n, h;

bool check(li maxh){
	li k = min(h, maxh);
	li cnt = maxh * maxh - k * (k - 1) / 2;
	return (cnt <= n);
}

li get(li maxh){
	li k = min(h, maxh);
	li cnt = maxh * maxh - k * (k - 1) / 2;
	li len = (2 * maxh - 1) - (k - 1);
	n -= cnt;
	return len + (n + maxh - 1) / maxh;
}

int main() {
	scanf("%lld%lld", &n, &h);
	li l = 1, r = INF;
	
	while (l < r - 1){
		li m = (l + r) / 2;
		
		if (check(m))
			l = m;
		else
			r = m;
	}
	
	printf("%lld\n", check(r) ? get(r) : get(l));
	return 0;
}

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

const int N = 500 * 1000 + 13;

int f[N];

void upd(int x){
    for (int i = x; i < N; i |= i + 1)
        ++f[i];
}

int sum(int x){
    int res = 0;
    for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
        res += f[i];
    return res;
}

int get(int l, int r){
	if (l > r) return 0;
	return sum(r) - sum(l - 1);
}

int main(){
	int n, k, dif;
	scanf("%d%d%d", &n, &k, &dif);
	vector<int> a(n);
	forn(i, n)
		scanf("%d", &a[i]);
	sort(a.begin(), a.end());
	
	vector<int> dp(n + 1, 0);
	
	dp[0] = 1;
	upd(0);
	
	int l = 0;
	forn(i, n){
		while (l < i && a[i] - a[l] > dif)
			++l;
		dp[i + 1] = (get(l, i - k + 1) >= 1);
		if (dp[i + 1]) upd(i + 1);
	}
	
	puts(dp[n] ? "YES" : "NO");
}

#include <bits/stdc++.h>

#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

using namespace std;

const int B = 2;

typedef array<int, B> ht;

ht MOD, BASE;

inline int norm(int a, const int &MOD) {
	while(a >= MOD)
		a -= MOD;
	while(a < 0)
		a += MOD;
	return a;
}

inline int mul(int a, int b, const int &MOD) {
	return int(a * 1ll * b % MOD);
}

inline ht operator +(const ht &a, const ht &b) {
	ht ans;
	fore(i, 0, sz(ans))
		ans[i] = norm(a[i] + b[i], MOD[i]);
	return ans;
}

inline ht operator -(const ht &a, const ht &b) {
	ht ans;
	fore(i, 0, sz(ans))
		ans[i] = norm(a[i] - b[i], MOD[i]);
	return ans;
}

inline ht operator *(const ht &a, const ht &b) {
	ht ans;
	fore(i, 0, sz(ans))
		ans[i] = mul(a[i], b[i], MOD[i]);
	return ans;
}

int CMODS[] = {int(1e9) + 7, int(1e9) + 9, int(1e9) + 21, int(1e9) + 33, int(1e9) + 87, int(1e9) + 93, int(1e9) + 97, int(1e9) + 103};
int CBASE[] = {1009, 1013, 1019, 1021};

const int N = 200 * 1000 + 555;

int n, m;
char s[N];
int x[N], y[N], len[N];

inline bool read() {
	if(!(cin >> n >> m))
		return false;
	assert(scanf("%s", s) == 1);
	
	fore(i, 0, m) {
		assert(scanf("%d%d%d", &x[i], &y[i], &len[i]) == 3);
		x[i]--, y[i]--;
	}
	return true;
}
void setMods() {
	mt19937 rnd;
	unsigned int seed = n;
	fore(i, 0, n)
		seed = (seed * 3) + s[i];
	fore(i, 0, m) {
		seed = (seed * 3) + x[i];
		seed = (seed * 3) + y[i];
		seed = (seed * 3) + len[i];
	}
	rnd.seed(seed);
	
	set<int> mids;
	while(sz(mids) < sz(MOD))
		mids.insert(rnd() % 8);
	vector<int> vmids(mids.begin(), mids.end());
	fore(i, 0, sz(MOD)) {
		MOD[i] = CMODS[vmids[i]];
		BASE[i] = CBASE[i];
	}
}

ht pBase[N];
ht ph[27][N];
vector<int> ord[N];

ht getHash(int id, int l, int r) {
	return ph[id][r] - ph[id][l] * pBase[r - l];
}

inline void solve() {
	setMods();
	
	pBase[0] = {1, 1};
	fore(i, 1, N)
		pBase[i] = pBase[i - 1] * BASE;
		
	fore(c, 0, 26) {
		ph[c][0] = {0, 0};
		fore(i, 0, n) {
			int val = (s[i] == c + 'a');
			ph[c][i + 1] = ph[c][i] * BASE + ht{val, val};
		}
	}
	
	vector<int> curOrd(26, 0);
	iota(curOrd.begin(), curOrd.end(), 0);
	for(int i = n - 1; i >= 0; i--) {
		ord[i] = curOrd;
		auto it = find(ord[i].begin(), ord[i].end(), int(s[i] - 'a'));
		ord[i].erase(it);
		ord[i].insert(ord[i].begin(), int(s[i] - 'a'));
		curOrd = ord[i];
	}
	
	fore(q, 0, m) {
		int s1 = x[q], s2 = y[q];
		bool ok = true;
		
		fore(i, 0, 26) {
			if(getHash(ord[s1][i], s1, s1 + len[q]) != 
				getHash(ord[s2][i], s2, s2 + len[q])) {
				ok = false;
				break;
			}
		}
		puts(ok ? "YES" : "NO");
	}
}

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

#include <bits/stdc++.h>

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

using namespace std;

typedef unsigned long long uli;

const int N = 200 * 1000 + 555;

int n, m;
uli a, b, c;
vector<int> g[N];

inline bool read() {
	if(!(cin >> n >> m))
		return false;
	assert(cin >> a >> b >> c);
	fore(i, 0, m) {
		int u, v;
		assert(scanf("%d%d", &u, &v) == 2);
		
		g[u].push_back(v);
		g[v].push_back(u);
	}
	return true;
}

vector<uli> ps[N];

inline uli getSum(int v, int l, int r) {
	return ps[v][r] - ps[v][l];
}

const int MX = 700;
int id[N];

const int B = 1111;
bitset<N> has[B];
int szh = 0;

inline void solve() {
	memset(id, -1, sizeof id);
	szh = 0;
	fore(v, 0, n) {
		sort(g[v].begin(), g[v].end());
		
		ps[v].assign(sz(g[v]) + 1, 0);
		fore(i, 0, sz(g[v]))
			ps[v][i + 1] = ps[v][i] + g[v][i];
		
		if(sz(g[v]) >= MX) {
			assert(szh < B);
			id[v] = szh++;
			
			for(int to : g[v])
				has[id[v]][to] = 1;
		}
	}
	
	uli all = 0;
	fore(v, 0, n) {
		uli lw = v, gr = n - v - 1;
		all += a * v * (gr * (gr - 1) / 2);
		all += b * v * (lw * gr);
		all += c * v * (lw * (lw - 1) / 2);
	}
	
	uli sub1 = 0;
	fore(v, 0, n) {
		for(int to : g[v]) {
			if(to > v)
				break;
			
			uli cnt = to;
			uli sum = cnt * (cnt - 1) / 2;
			sub1 += a * sum + cnt * (b * to + c * v);
			
			cnt = v - to - 1;
			sum = (2 * to + cnt + 1) * cnt / 2;
			sub1 += b * sum + cnt * (a * to + c * v);
		}
		
		uli sum = 0;
		fore(i, 0, sz(g[v])) {
			if(g[v][i] > v)
				break;
			
			uli cnt = i;
			sub1 -= a * sum + cnt * (b * g[v][i] + c * v);
			sum += g[v][i];
		}
	}
	all -= sub1;
	
	uli sub2 = 0;
	uli cntE = 0, sumE = 0;
	fore(v, 0, n) {
		sub2 += sumE + cntE * c * v;
		for(int to : g[v]) {
			if(to > v)
				break;
			
			cntE++;
			sumE += a * to + b * v;
		}
	}
	
	fore(v, 0, n) {
		for(int to : g[v]) {
			if(to > v)
				break;
			
			int pos = int(lower_bound(g[to].begin(), g[to].end(), to) - g[to].begin());
			sub2 -= a * getSum(to, 0, pos) + pos * (b * to + c * v);
			
			int pos2 = int(lower_bound(g[to].begin(), g[to].end(), v) - g[to].begin());
			sub2 -= b * getSum(to, pos, pos2) + (pos2 - pos) * (a * to + c * v);
		}
	}
	
	vector<char> curh(n + 5, 0);
	fore(v, 0, n) {
		if(id[v] == -1) {
			fore(i2, 0, sz(g[v])) {
				int u2 = g[v][i2];
				if(u2 > v)
					break;
				
				if(id[u2] != -1) {
					fore(i1, 0, i2) {
						int u1 = g[v][i1];
						if(has[id[u2]][u1])
							sub2 += a * u1 + b * u2 + c * v;
					}
				} else {
					for(int to : g[u2]) {
						if(to > u2)
							break;
						curh[to] = 1;
					}
					fore(i1, 0, i2) {
						int u1 = g[v][i1];
						if(curh[u1])
							sub2 += a * u1 + b * u2 + c * v;
					}
					for(int to : g[u2]) {
						if(to > u2)
							break;
						curh[to] = 0;
					}
				}
			}
		} else {
			fore(u2, 0, v) {
				if(!has[id[v]][u2])
					continue;
				for(int u1 : g[u2]) {
					if(u1 > u2)
						break;
					if(has[id[v]][u1])
						sub2 += a * u1 + b * u2 + c * v;
				}
			}
		}
	}
	all -= sub2;
	cout << all << endl;
}

int main(){
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(10);

	if(read()) {
		solve();
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
#endif
	}
	return 0;
}