#include <bits/stdc++.h>

using namespace std;

string s;

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

#include <bits/stdc++.h>

using namespace std;

const int N = 109;

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

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

    dfs(0, 0);

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

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef long long li;

mt19937 rnd(time(NULL));

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

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

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

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

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

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

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

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

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

set<int> free_pos;

const int N = 400043;

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

li start_sum = 0;
li end_sum = 0;

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

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

#include <bits/stdc++.h>

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

using namespace std;

const int N = 1000 + 7;

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

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

#include <bits/stdc++.h>

using namespace std;

const int N = 300 * 1000 + 9;

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

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

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

using namespace std;

const int N = 109;

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

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

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

const int N = 200 * 1000 + 555;

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

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

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

li ps[N];

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

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

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

#include <bits/stdc++.h>

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

using namespace std;

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

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

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

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

long long dif;
long long mn;

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

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

#include<bits/stdc++.h>

using namespace std;

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

int n, q;

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

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

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

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

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

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

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

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

#include <bits/stdc++.h>

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

using namespace std;


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

#include<bits/stdc++.h>

using namespace std;

int n, M;
vector<int> a;

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

vector<int> f[2];

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

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

#include <bits/stdc++.h>

using namespace std;

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

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

const int N = 500043;

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

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

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

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

typedef pair<int, int> pt;

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

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

typedef node* stree;

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

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

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

typedef pair<int, int> pt;

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

const int M = 60 * N;

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

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

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

pt curans;

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

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

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

int last[N];

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

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

#define x first
#define y second

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

li f[N];

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

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

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

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

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

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

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

Hint: When does some vowel stay in string?

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

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

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

Model solution

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

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

More hints

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

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

Solution

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

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

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

and then it equals to:

and now let's take out the l_i! ,

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

and it is easy to see it equals to:

and using the fact that

it will equal to:

So the final answer will equal to:

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

There is also another solution that you can read here.

Model solution

Let's denote n = |s|.

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

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

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

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

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

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

Model solution