#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        string s; cin >> s;
        int odd = 0;
        for (char c : s) if ((c - '0') & 1) odd++;
        if (odd <= 1) { cout << "-1\n"; continue; }
        int cnt = 0;
        for (char c : s) {
            if ((c - '0') & 1) { cout << c; cnt++; }
            if (cnt == 2) break;
        }
        cout << '\n';
    }
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int nbTests; cin >> nbTests;
    while (nbTests--) {
	    int nbElem; cin >> nbElem;
	    vector<int> tab(nbElem);

	    for (int i = 0; i < nbElem; ++i)
		    cin >> tab[i];

	    int prefixEnd = -1, suffixEnd = nbElem;

	    for (int i = 0; i < nbElem; ++i) {
		    if (tab[i] < i) break;
		    prefixEnd = i;
	    }
	    for (int i = nbElem-1; i >= 0; --i) {
		    if (tab[i] < (nbElem-1)-i) break;
		    suffixEnd = i;
	    }

	    if (suffixEnd <= prefixEnd) // Non-empty intersection
		    cout << "Yes\n";
	    else
		    cout << "No\n";
    }
}

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

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int nbTests; cin >> nbTests;
    while (nbTests--) {
	    int nbElem, pos, nbControl;
	    cin >> nbElem >> pos >> nbControl;

	    int before = pos-1, behind = nbElem-pos;
	    nbControl = min(nbControl, before);

	    vector<int> tab(nbElem);
	    for (int i = 0; i < nbElem; ++i) cin >> tab[i];

	    int bestStrategy = 0;

	    for (int orderFirst = 0; orderFirst <= nbControl; ++orderFirst) {
		    int strategyAns = (int)(1e9) + 5;
		    for (int opponentFirst = 0; opponentFirst <= before-nbControl; ++opponentFirst) {
			    int caseAns = max(tab[orderFirst + opponentFirst], tab[orderFirst + opponentFirst + behind]); 
			    strategyAns = min(strategyAns, caseAns);
		    }
		    bestStrategy = max(bestStrategy, strategyAns);
	    }

	    cout << bestStrategy << "\n";
    }
}

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

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    k = min(k, m - 1);
    vector<int> a(n);
    for(auto &x : a)
        cin >> x;
    vector<int> b;
    for(int i = 0; i < m; i++)
        b.push_back(max(a[i], a[i + n - m]));
    int sz = m - k;
    int ans = 0;
    deque<int> q;
    for(int i = 0, j = 0; i + sz - 1 < m; i++) {
        while(q.size() && q.front() < i)
            q.pop_front();
        while(j < i + sz) {
            while(q.size() && b[q.back()] >= b[j])
                q.pop_back();
            q.push_back(j++);
        }
        ans = max(ans, b[q.front()]);
    }
    cout << ans << '\n';
}

int main() {
    int t;
    cin >> t;
    while(t--)
        solve();
}

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

const int N = 200005;

char s[N];
int n, q, l, r, sum[N][26];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> (s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 26; j++) {
            sum[i][j] = sum[i - 1][j];
        }
        sum[i][s[i] - 'a']++;
    }
    cin >> q;
    while (q--) {
        cin >> l >> r;
        int cnt = 0;
        for (int i = 0; i < 26; i++) {
            cnt += (sum[r][i] - sum[l - 1][i] > 0);
        }
        if (l == r || cnt >= 3 || s[l] != s[r]) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int lim = 1000*1000 + 5;
int nbElem, nbSub;
vector<int> subset[lim];
int side[lim];
int isIn[lim][2];
string ini;
int rep = 0;

int drepr[lim]; 
int dsz[lim];
int cnt[lim][2];

int dfind(int x)
{
    if (drepr[x] != x) drepr[x] = dfind(drepr[x]);
    return drepr[x];
}

void add(int cc, int s0, int s1)
{
    cc = dfind(cc);
    rep -= min(cnt[cc][0], cnt[cc][1]);
    cnt[cc][0] = min(lim, cnt[cc][0] + s0);
    cnt[cc][1] = min(lim, cnt[cc][1] + s1);
    rep += min(cnt[cc][0], cnt[cc][1]);
}

void dmerge(int a, int b)
{
    a = dfind(a); b = dfind(b);
    if (a == b) return;
    if (dsz[a] < dsz[b]) swap(a,b);
    add(a, cnt[b][0], cnt[b][1]);
    add(b, -cnt[b][0], -cnt[b][1]);
    dsz[a] += dsz[b];
    drepr[b] = a;
}

void dfs(int nod)
{
    cnt[nod][side[nod]] = 1;
    for (int elem : subset[nod]) {
	    if (isIn[elem][1] == -1) continue;
	    int oth = isIn[elem][0] + isIn[elem][1] - nod;
	    if (side[oth] == -1) {
		    side[oth] = side[nod] ^ (ini[elem] == '0');
		    dfs(oth);
	    }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> nbElem >> nbSub;
    cin >> ini;
    fill(side,side+lim,-1);
    iota(drepr,drepr+lim,0);
    fill_n(&isIn[0][0], 2*lim, -1);

    for (int sub = 0; sub < nbSub; ++sub) {
	    int st; cin >> st;
	    subset[sub].resize(st);
	    for (int pos = 0; pos < st; ++pos) {
		    int elem; cin >> elem; --elem;
		    subset[sub][pos] = elem;
		    if (isIn[elem][0] == -1) isIn[elem][0] = sub;
		    else isIn[elem][1] = sub;
	    }
    }

    for (int sub = 0; sub < nbSub; ++sub) {
	    if (side[sub] == -1) {
		    side[sub] = 0;
		    dfs(sub);
	    }
    }

    for (int elem = 0; elem < nbElem; ++elem) {
	    int n0 = isIn[elem][0], n1 = isIn[elem][1];
	    if (n0 != -1 && n1 == -1) {
		    int destroy = side[n0] ^ (ini[elem] == '0');
		    if (destroy == 1) add(n0, 0, lim);
		    else add(n0, lim, 0);	
	    } else if (n0 != -1) {
		    dmerge(n0, n1);
	    }
	    cout << rep << "\n";
    }
}

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int N = 1E6 + 5, K = 1E6 + 5, INF = 1E9 + 7;

int n, k, c, v, ans = 0, dsu[K];
char s[N];
vector<int> adj[N];

struct node {
    int l, r, xo;

    node(int _l = 0, int _r = 0, int _xo = 0) : l(_l), r(_r), xo(_xo) {}

    int get() {
        return min(l, r);
    }

    inline void operator+=(node oth) {
        l = min(INF, l + oth.l);
        r = min(INF, r + oth.r);
    }
} val[K];

pair<int, int> trace(int u) {
    if (dsu[u] < 0) {
        return {u, 0};
    } else {
        pair<int, int> tmp = trace(dsu[u]);
        dsu[u] = tmp.fi;
        val[u].xo ^= tmp.se;
        return {dsu[u], val[u].xo};
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k >> (s + 1);
    for (int i = 1; i <= k; i++) {
        dsu[i] = -1;
        val[i] = node(1, 0, 0);
        cin >> c;
        while (c--) {
            cin >> v;
            adj[v].push_back(i);
        }
    }
    for (int i = 1; i <= n; i++) {
        int typ = (s[i] - '0') ^ 1;
        if (ans != -1) {
            if (adj[i].size() == 1) {
                pair<int, int> u = trace(adj[i][0]);
                ans -= val[u.fi].get();
                val[u.fi] += node((u.se == typ) * INF, (u.se != typ) * INF);
                ans += val[u.fi].get();
            } else if (adj[i].size() == 2) {
                pair<int, int> u = trace(adj[i][0]);
                pair<int, int> v = trace(adj[i][1]);
                if (u.fi != v.fi) {
                    ans -= val[u.fi].get() + val[v.fi].get();
                    if (dsu[u.fi] > dsu[v.fi]) {
                        swap(u, v);
                    }
                    if (u.se ^ v.se ^ typ) {
                        swap(val[v.fi].l, val[v.fi].r);
                        val[v.fi].xo = 1;
                    }
                    dsu[u.fi] += dsu[v.fi];
                    dsu[v.fi] = u.fi;
                    val[u.fi] += val[v.fi];
                    ans += val[u.fi].get();
                }
            }
        }
        cout << ans << '\n';
    }
}

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

bool ask(int pos)
{
    cout << "? " << pos+1 << endl << flush;
    char c; cin >> c;
    if (c == 'E') exit(0);
    return (c == 'Y');
}

int main()
{
    int nbElem, memSize, nbBlocks;
    cin >> nbElem >> memSize;
    nbBlocks = nbElem / memSize;

    vector<bool> isAlive(nbElem, true);

    for (int startBlock = 0; startBlock < nbBlocks; ++startBlock) {
	    int delta = 0;
	    cout << "R" << endl << flush;
	    for (int iDo = 0; iDo < nbBlocks; ++iDo) {
		    int curBlock = (startBlock+delta+nbBlocks) % nbBlocks;
		    int st = curBlock*memSize;
		    for (int elem = st; elem < st+memSize; ++elem) {
			    if (isAlive[elem]) {
				    if (ask(elem)) isAlive[elem] = false;
			    }
		    }

		    if (delta >= 0) ++delta;
		    delta = -delta;
	    }
    }

    int nbAlive = count(isAlive.begin(), isAlive.end(), true);
    cout << "! " << nbAlive << endl << flush;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+1;
const int ts=1<<21;
int n;
ll mx[ts],se[ts],mxc[ts];//max, 2nd max, max count
int sz;
ll ch[N];//which values are changed
ll df[N];//change in frequency
void pass(int id,int c){
    if(mx[c]>mx[id]) mx[c]=mx[id];
}
void push(int id){
    pass(id,id*2);
    pass(id,id*2+1);
}
void pull(int id){
    mx[id]=max(mx[id*2],mx[id*2+1]);
    mxc[id]=0;
    if(mx[id]==mx[id*2]) mxc[id]+=mxc[id*2];
    if(mx[id]==mx[id*2+1]) mxc[id]+=mxc[id*2+1];
    se[id]=max(se[id*2],se[id*2+1]);
    if(mx[id*2]!=mx[id]) se[id]=max(se[id],mx[id*2]);
    if(mx[id*2+1]!=mx[id]) se[id]=max(se[id],mx[id*2+1]);
}
void upd(int id,int l,int r,int ql,int qr,int v){
    if(l>qr || r<ql || mx[id]<=v) return;
    if(ql<=l && r<=qr && se[id]<v){
	    ch[++sz]=mx[id];df[mx[id]]-=mxc[id];
	    mx[id]=v;
	    ch[++sz]=mx[id];df[mx[id]]+=mxc[id];
	    return;
    }
    push(id);
    int mid=(l+r)/2;
    upd(id*2,l,mid,ql,qr,v);
    upd(id*2+1,mid+1,r,ql,qr,v);
    pull(id);
}
void upd2(int id,int l,int r,int p,int v){
    if(l==r){
	    ch[++sz]=mx[id];df[mx[id]]-=mxc[id];
	    mx[id]=v;
	    ch[++sz]=mx[id];df[mx[id]]+=mxc[id];
	    return;
    }
    push(id);
    int mid=(l+r)/2;
    if(p<=mid) upd2(id*2,l,mid,p,v);
    else upd2(id*2+1,mid+1,r,p,v);
    pull(id);
}
void build(int id,int l,int r){
    mx[id]=0;mxc[id]=r-l+1;se[id]=-1e9;
    if(l==r) return;
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
}
/////////////////////////////////////////////////
ll bit1[N],bit2[N];
void bupd1(int id,ll v){
    for(int i=id; i<=n ;i+=i&-i) bit1[i]+=v;
}
void bupd2(int id,ll v){
    for(int i=id; i<=n ;i+=i&-i) bit2[i]+=v;
}
ll bqry1(int id){
    ll res=0;
    for(int i=id; i>=1 ;i-=i&-i) res+=bit1[i];
    return res;
}
ll bqry2(int id){
    ll res=0;
    for(int i=id; i>=1 ;i-=i&-i) res+=bit2[i];
    return res;
}
int a[N],p[N];
ll ans[N];
set<int>s,t;
void magic(int mg){
    s.clear();t.clear();build(1,1,n);
    for(int i=1; i<=n ;i++) bit1[i]=bit2[i]=0;
    s.insert(p[1]);//set of existed elements
    t.insert(p[1]);//set of l that maxr[] is not null
    bupd1(p[1],1);
    int mx=p[1];//largest existed position
    upd2(1,1,n,p[1],p[1]);
    bupd2(p[1],-1);
    ll tot=-1;
    for(int i=2; i<=n ;i++){
	    int cur=p[i];
	    auto it=s.lower_bound(cur);
	    bool rm=(it==s.end());//new element is rightmost
	    int nxt=0;
	    if(!rm) nxt=*it;//next
	    if(it==s.begin()){//new element is leftmost
		    tot-=bqry1(cur);bupd2(cur,-1);
		    t.insert(cur);
		    upd2(1,1,n,cur,mx);
	    }
	    else{
		    int prv=*(--it);
		    upd(1,1,n,1,prv,prv);
		    if(rm) mx=cur;
		    else{
			    upd2(1,1,n,nxt,mx);
			    if(t.find(nxt)==t.end()){
				    tot-=bqry1(nxt);bupd2(nxt,-1);
				    t.insert(nxt);
			    }
		    }
		    upd2(1,1,n,*s.begin(),mx);
	    }
	    s.insert(cur);
	    tot+=bqry2(n)-bqry2(cur-1);
	    bupd1(cur,1);
	    for(int j=1; j<=sz ;j++){
		    if(ch[j]!=0 && df[ch[j]]!=0){
			    tot+=df[ch[j]]*bqry1(ch[j]);
			    bupd2(ch[j],df[ch[j]]);
			    df[ch[j]]=0;
		    }
	    }
	    sz=0;
	    ans[i]+=tot;
    }
}
void solve(){
    for(int i=1; i<=n ;i++){
	    p[a[i]]=i;ans[i]=0;
    }
    magic(1);
    for(int i=1; i<=n ;i++) p[i]=n+1-p[i];
    magic(0);
    for(int i=1; i<=n ;i++) ans[i]+=1;
    for(int i=1; i<=n ;i++) cout << ans[i] << '\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i=1; i<=n ;i++) cin >> a[i];
    solve();
}

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

const int N = 5, MX = 4 * N, LG = 31, MOD = 998244353;

int n, m, x[N], y[N];
int px[1 << N], nx[1 << N], py[1 << N], ny[1 << N];
int dp[LG][MX][MX][MX][MX][2][2];

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    for (int msk = 0; msk < (1 << n); msk++) {
        for (int i = 0; i < n; i++) {
            if (msk >> i & 1) {
                (x[i] < 0 ? nx : px)[msk] += abs(x[i]);
                (y[i] < 0 ? ny : py)[msk] += abs(y[i]);
            }
        }
    }
    int mpx = max(1, px[(1 << n) - 1]);
    int mpy = max(1, py[(1 << n) - 1]);
    int mnx = max(1, nx[(1 << n) - 1]);
    int mny = max(1, ny[(1 << n) - 1]);
    dp[0][0][0][0][0][0][0] = 1;
    for (int lg = 0; (1 << lg) <= m; lg++) {                                // bit position
        for (int cpx = 0; cpx < mpx; cpx++) {                               // carry of positive x
            for (int cpy = 0; cpy < mpy; cpy++) {                           // carry of positive y
                for (int cnx = 0; cnx < mnx; cnx++) {                       // carry of negative x
                    for (int cny = 0; cny < mny; cny++) {                   // carry of negative y
                        for (int sx = 0; sx < 2; sx++) {                    // is the suffix of x greater than the suffix of m
                            for (int sy = 0; sy < 2; sy++) {                // is the suffix of y greater than the suffix of m
                                for (int msk = 0; msk < (1 << n); msk++) {  // iterating over the mask of the current bit position
                                    int spx = cpx + px[msk];
                                    int spy = cpy + py[msk];
                                    int snx = cnx + nx[msk];
                                    int sny = cny + ny[msk];
                                    if (((spx ^ snx) & 1) || ((spy ^ sny) & 1)) {
                                        continue;
                                    }
                                    int bx = spx & 1, by = spy & 1;
                                    int nsx = (bx < (m >> lg & 1) ? 0 : bx > (m >> lg & 1) ? 1 : sx);
                                    int nsy = (by < (m >> lg & 1) ? 0 : by > (m >> lg & 1) ? 1 : sy);
                                    add(dp[lg + 1][spx / 2][spy / 2][snx / 2][sny / 2][nsx][nsy], dp[lg][cpx][cpy][cnx][cny][sx][sy]);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << (dp[__lg(m) + 1][0][0][0][0][0][0] + MOD - 1) % MOD << '\n';
}

Oh boi this is gonna be interesting ( ͡° ͜ʖ ͡°)

The theme of the contest can be found by concatenating the first letter of each paragraph of the announcement ( ͡° ͜ʖ ͡°) From now on, we will refer to six-digit codes found in each problem statement as "sauce". ( ͡° ͜ʖ ͡°)

For 1291A - Even But Not Even, the obvious sauces are $$$177013$$$ and $$$265918$$$. Along with this, break down the really long number in the sample input, you will get 4 sauces: $$$222373$$$, $$$204424$$$, $$$185217$$$, and $$$171912$$$.

For 1291B - Array Sharpening, the sauces are $$$282865$$$, $$$256988$$$ (found as inline examples for non-sharpened arrays), and $$$248618$$$ (found in the sample input).

For 1290A - Mind Control, the sauces are $$$292385$$$ and $$$213604$$$ (found in the sample input).

For 1290B - Irreducible Anagrams, look at the second sample input. There are 6 queries, concatenate $$$l$$$ and $$$r$$$ of all queries to get $$$122153$$$ and $$$242975$$$.

For 1290C - Prefix Enlightenment, the binary string of the last sample input encodes a sauce into binary. Decode it into decimal to get $$$299782$$$. Fun side note, while developing this problem, the intended sauce was $$$299742$$$, but I typed in the wrong code to the binary converter. It turned out to be better btw. ( ͡° ͜ʖ ͡°)

For 1290D - Coffee Varieties (hard version), the ? queries of the second sample output gives you $$$264525$$$. Additionally, the ! query gives you page $$$6$$$ of the sauce. ( ͡° ͜ʖ ͡°)

For 1290E - Cartesian Tree , the permutation of the second sample input gives you $$$124563$$$.

For 1290F - Making Shapes, the third sample output gives you the sauce $$$296161$$$.

UPD: As I write these lines, $$$300000$$$ has been born. So unironically, the constraints of 1291B - Array Sharpening and 1290C - Prefix Enlightenment are now sauces. ( ͡° ͜ʖ ͡°)

Hope you have fun with the easter eggs we provided. ( ͡~ ͜ʖ ͡°)

#include <iostream>

using namespace std;

int main ()
{
    int n, m;
	cin >> n >> m;
	cout << (m ? min(m, n - m) : 1) << endl;
	return 0;
}

#include <iostream>
#include <stdio.h>
using namespace std;

const int N = 1e5 + 10;

int n, color, ans, mx, f[N], cnt[N];

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
    {
        scanf("%d", &color);
        cnt[f[color]]--;
        f[color]++;
        cnt[f[color]]++;
        mx = max(mx, f[color]);
        bool ok = false;
        if (cnt[1] == i) // every color has occurence of 1
            ok = true;
        else if (cnt[i] == 1) // only one color has the maximum occurence and the occurence is i
            ok = true;
        else if (cnt[1] == 1 && cnt[mx] * mx == i - 1) // one color has occurence of 1 and other colors have the same occurence
            ok = true;
        else if (cnt[mx - 1] * (mx - 1) == i - mx && cnt[mx] == 1) // one color has the occurence 1 more than any other color
            ok = true;
        if (ok)
            ans = i;
    }
    printf("%d", ans);
	return 0;
}

#include <cstdio>
#include <map>
#include <set>
#include <utility>
const int N = 1001;
int x[N], y[N];
std::map<std::pair<int,int>,std::set<long long>> slope_map;

int gcd(int a, int b) 
{
	if (a == 0)
		return b;
	return gcd(b % a, a);
}

int main()
{
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d%d", &x[i], &y[i]);
	long long total = 0, res = 0;
	for (int i = 1; i <= n - 1; ++i)
		for (int j = i + 1; j <= n; ++j)
		{
			int x1 = x[i], y1 = y[i], x2 = x[j], y2 = y[j];
			// construct a line passing through (x1, y1) and (x2, y2)
			// line is expressed as equation ax - by = c with constant a, b, c 
			int a = y1 - y2, b = x1 - x2;
			// simplify equation
			int d = gcd(a, b); a /= d, b /= d;
			if (a < 0 || (a == 0 && b < 0))
			{
			    a = -a;
			    b = -b;
			}
			// lines with the same slope (same a, b) are stored in a map
			std::pair<int,int> slope(a, b);
			long long c = 1LL * a * x1 - 1LL * b * y1;
			if (!slope_map[slope].count(c))
			{
				++total;
				slope_map[slope].insert(c);
				// if this line is new, it intersects every line with different slope
				res += total - slope_map[slope].size();
			}
		}
	printf("%lld\n", res);
}

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int K = 1005, N = 55, M = 55, INF = 1E9 + 7;

int k, n, m;
int kmp_s[N], nxt_s[N][26], kmp_t[M], nxt_t[M][26];
int dp[K][N][M];
char code[K], s[N], t[M];

void init(char s[], int n, int kmp[], int nxt[][26])
{
    kmp[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        int cur = kmp[i - 1];
        while (cur > 0 && s[cur + 1] != s[i])
            cur = kmp[cur];
        if (s[cur + 1] == s[i])
            ++cur;
        kmp[i] = cur;
    }

    for (int i = 0; i <= n; i++)
        for (char c = 'a'; c <= 'z'; c++)
        {
            int cur = i;
            while (cur > 0 && s[cur + 1] != c)
                cur = kmp[cur];
            if (s[cur + 1] == c)
                ++cur;
            nxt[i][c - 'a'] = cur;
        }
}

int main()
{
    scanf("%s%s%s", code + 1, s + 1, t + 1);
    k = strlen(code + 1); n = strlen(s + 1); m = strlen(t + 1);
    init(s, n, kmp_s, nxt_s); init(t, m, kmp_t, nxt_t);
    for (int i = 0; i <= k; i++)
        for (int ks = 0; ks <= n; ks++)
            for (int kt = 0; kt <= m; kt++)
                dp[i][ks][kt] = -INF;
    dp[0][0][0] = 0;
    for (int i = 0; i < k; i++)
        for (int ks = 0; ks <= n; ks++)
            for (int kt = 0; kt <= m; kt++)
                for (char c = 'a'; c <= 'z'; c++)
                    if (code[i + 1] == '*' || code[i + 1] == c) // we now add/replace the (i + 1)-th character
                    {
                        int ns = nxt_s[ks][c - 'a'], nt = nxt_t[kt][c - 'a'];
                        int tmp = dp[i][ks][kt] + (ns == n) - (nt == m); // add the new occurrences if any
                        dp[i + 1][ns][nt] = max(dp[i + 1][ns][nt], tmp);
                    }
    int ma = -INF;
    for (int ks = 0; ks <= n; ks++)
        for (int kt = 0; kt <= m; kt++)
            ma = max(ma, dp[k][ks][kt]);
    printf("%d\n", ma);
}

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 200005;

int n, a[N];
vector<int> basis, vec;

void add(int u)
{
    int tmp = u;
    // we keep the basis sorted in decreasing order
    for (int &v : basis)
        u = min(u, u ^ v);
    if (u > 0) // u is a new element in the basis
    {
        basis.push_back(u);
        vec.push_back(tmp);
        // now we move u up until the basis is decreasingly sorted again
        for (int i = basis.size() - 1; i > 0; i--)
            if (basis[i] > basis[i - 1])
                swap(basis[i], basis[i - 1]);
            else
                break;
    }
}

void gray_code(int size)
{
    vector<int> ans = {0};
    for (int i = 0; i < size; i++)
        for (int j = (1 << i) - 1; j >= 0; j--)
            ans.push_back(ans[j] ^ vec[i]);
    for (int &v : ans)
        printf("%d ", v);
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", a + i);
    sort(a, a + n);
    int pt = 0, x = 0;
    for (int i = 1; i < 20; i++)
    {
        for (; pt < n && a[pt] < (1 << i); pt++)
            add(a[pt]);
        if (basis.size() == i)
            x = i;
    }
    basis.clear();
    vec.clear();
    for (int i = 0; i < n && a[i] < (1 << x); i++)
        add(a[i]);
    printf("%d\n", x);
    gray_code(x);
}

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 200005, MX = 1E6 + 5;

int n, x = 0, a[N];
bool vis[MX];
vector<int> basis, vec, ans;

void add(int u)
{
    int tmp = u;
    for (int &v : basis)
        u = min(u, u ^ v);
    if (u > 0)
    {
        basis.push_back(u);
        vec.push_back(tmp);
        for (int i = basis.size() - 1; i > 0; i--)
            if (basis[i] > basis[i - 1])
                swap(basis[i], basis[i - 1]);
            else
                break;
    }
}

void DFS(int u, int it = 0)
{
    ans.push_back(u);
    vis[u] = true;
    if (it == (1 << x) - 1)
        return;
    for (int &v : vec)
        if (!vis[u ^ v])
        {
            DFS(u ^ v, it + 1);
            return;
        }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", a + i);
    sort(a, a + n);
    int pt = 0;
    for (int i = 1; i < 20; i++)
    {
        for (; pt < n && a[pt] < (1 << i); pt++)
            add(a[pt]);
        if (basis.size() == i)
            x = i;
    }
    basis.clear();
    vec.clear();
    for (int i = 0; i < n && a[i] < (1 << x); i++)
        add(a[i]);
    printf("%d\n", x);
    DFS(0);
    for (int &v : ans)
        printf("%d ", v);
}

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int N = 2E5 + 5, M = 2E5 + 5;
const long long INF = 1E18 + 7;

int n, m, q, ed, nw, mx, u[M], v[M], w[M], ind[M];
int tr[N], le[N], ri[N];
bool on_path[N];
long long dis[2][N];

struct TNode
{
    int u;
    long long val;

    TNode(int _u, long long _val)
    {
        u = _u;
        val = _val;
    }

    inline bool operator>(const TNode &oth) const
    {
        return val > oth.val;
    }
};
priority_queue<TNode, vector<TNode>, greater<TNode>> pq;

struct TEdge
{
    int v, w, ind;

    TEdge(int _v, int _w, int _ind)
    {
        v = _v;
        w = _w;
        ind = _ind;
    }
};
vector<TEdge> adj[N];

struct TTree
{
#define m (l + r) / 2
#define lc i * 2
#define rc i * 2 + 1

    long long tr[4 * M];

    void build(int l, int r, int i)
    {
        tr[i] = INF;
        if (l == r)
            return;
        build(l, m, lc);
        build(m + 1, r, rc);
    }

    void upd(int l, int r, int i, int L, int R, long long v)
    {
        if (l > R || r < L || L > R)
            return;
        if (L <= l && r <= R)
        {
            tr[i] = min(tr[i], v);
            return;
        }
        upd(l, m, lc, L, R, v);
        upd(m + 1, r, rc, L, R, v);
    }

    long long que(int l, int r, int i, int u)
    {
        if (l == r)
            return tr[i];
        return min(tr[i], u <= m ? que(l, m, lc, u) : que(m + 1, r, rc, u));
    }

#undef m
#undef lc
#undef rc
} seg;

void dijkstra(int st, long long dis[], int get = 0)
{
    fill(dis + 1, dis + n + 1, INF);
    pq.push(TNode(st, dis[st] = 0));
    while (!pq.empty())
    {
        TNode u = pq.top(); pq.pop();
        if (u.val > dis[u.u])
            continue;
        for (TEdge &v : adj[u.u])
            if (dis[v.v] > u.val + v.w)
            {
                tr[v.v] = v.ind;
                if (get == 1 && !on_path[v.v])
                    le[v.v] = le[u.u];
                else if (get == 2 && !on_path[v.v])
                    ri[v.v] = ri[u.u];
                pq.push(TNode(v.v, dis[v.v] = u.val + v.w));
            }
    }
}

void trace()
{
    on_path[1] = true; le[1] = ri[1] = 0;
    for (int i = 1, cur = 1; cur != n; i++)
    {
        int edge = tr[cur];
        ind[edge] = mx = i;
        cur = u[edge] ^ v[edge] ^ cur;
        on_path[cur] = true;
        le[cur] = ri[cur] = i;
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", u + i, v + i, w + i);
        ind[i] = -1;
        adj[u[i]].push_back(TEdge(v[i], w[i], i));
        adj[v[i]].push_back(TEdge(u[i], w[i], i));
    }
    dijkstra(n, dis[1]); // reverse the initial dijkstra for the trace to increase from 1 -> n
    trace();
    dijkstra(1, dis[0], 1);
    dijkstra(n, dis[1], 2);
    seg.build(1, mx, 1);
    for (int i = 1; i <= m; i++)
        if (ind[i] == -1)
        {
            seg.upd(1, mx, 1, le[u[i]] + 1, ri[v[i]], dis[0][u[i]] + w[i] + dis[1][v[i]]);
            seg.upd(1, mx, 1, le[v[i]] + 1, ri[u[i]], dis[0][v[i]] + w[i] + dis[1][u[i]]);
        }
    while (q--)
    {
        scanf("%d%d", &ed, &nw);
        long long ans;
        if (ind[ed] > 0)
        {
            ans = dis[0][n] - w[ed] + nw;
            if (nw > w[ed])
                ans = min(ans, seg.que(1, mx, 1, ind[ed]));
        }
        else
        {
            ans = dis[0][n];
            if (nw < w[ed])
            {
                ans = min(ans, dis[0][u[ed]] + nw + dis[1][v[ed]]);
                ans = min(ans, dis[0][v[ed]] + nw + dis[1][u[ed]]);
            }
        }
        printf("%lld\n", ans);
    }
}