# Two Strings Game

### Problem Statement :

```Consider the following game for two players:

There are two strings A and B. Initially, some strings A' and B' are written on the sheet of paper. A' is always a substring of A and B' is always a substring of B. A move consists of appending a letter to exactly one of these strings: either to A' or to B'. After the move the constraint of A' being a substring of A and B' is a substring of B should still be satisfied. Players take their moves alternately. We call a pair (A', B') a position.

Two players are playing this game optimally. That means that if a player has a move that leads to his/her victory, he/she will definitely use this move. If a player is unable to make a move, he loses.

Alice and Bob are playing this game. Alice makes the first move. As always, she wants to win and this time she does a clever trick. She wants the starting position to be the Kth lexicographically winning position for the first player (i.e. her). Consider two positions (A'1, B'1) and (A'2, B'2). We consider the first position lexicographically smaller than the second if A1 is lexicographically smaller than A2, or if A1 is equal to A2 and B1 is lexicographically smaller than B2.

Please help her to find such a position, knowing the strings A, B and the integer K.

Note: An empty string has higher precedence than character "a"

Input Format

The first line of input consists of three integers, separated by a single space: N, M and K denoting the length of A, the length of B and K respectively. The second line consists of N small latin letters, corresponding to the string A. The third line consists of M small latin letters, corresponding to the string B.

Constraints

1 <= N, M <= 3 * 105
1 <= K <= 1018

Output Format

Output A' on the first line of input and B' on the second line of input. Please, pay attention that some of these strings can be empty. If there's no such pair, output "no solution" without quotes.```

### Solution :

```                            ```Solution in C :

In   C++  :

#include <bits/stdc++.h>

using namespace std;

const int maxn = 6e5;

string ans;
int mex_ans;

struct suffix_automaton
{
int len[maxn], link[maxn];
map<char, int> to[maxn];
int sz = 1, last;
void add_letter(char c)
{
int p = last;
last = sz++;
len[last] = len[p] + 1;
for(; !to[p][c]; p = link[p]) to[p][c] = last;
if(to[p][c] == last)
return;
int q = to[p][c];
if(len[q] == len[p] + 1)
{
link[last] = q;
return;
}
int cl = sz++;
to[cl] = to[q];
link[cl] = link[q];
len[cl] = len[p] + 1;
link[last] = link[q] = cl;
for(; to[p][c] == q; p = link[p]) to[p][c] = cl;
}

vector<int> top_sort[maxn];
int mex[maxn];
int mex_d[maxn];
int64_t total[maxn];
int64_t sum;

void dfs()
{
for(auto it: top_sort)
for(auto v: it)
{
vector<int> g;
for(auto it: to[v])
g.push_back(mex[it.second]);
for(auto it: g)
mex_d[it] = v + 1;
for(int i = 0; ; i++)
if(mex_d[i] != v + 1)
{
mex[v] = i;
break;
}
if(v == 0)
{
total[mex[v]]++;
sum++;
}
total[mex[v]] += len[v] - len[link[v]];
sum += len[v] - len[link[v]];
}
}

void build(string s)
{
for(auto c: s)
add_letter(c);
for(int i = 0; i < sz; i++)
top_sort[len[i]].push_back(i);
reverse(top_sort, top_sort + maxn);
dfs();
}

int64_t win[maxn];
int64_t win_cnt[maxn];

void rec_dfs(int v, int64_t &k)
{
if(win[v] >= k)
{
mex_ans = mex[v];
return;
}
else
{
k -= win[v];
}
for(auto it: to[v])
{
if(win_cnt[it.second] >= k)
{
ans += it.first;
rec_dfs(it.second, k);
return;
}
else
{
k -= win_cnt[it.second];
}
}
}
} sa1, sa2;

const int64_t inf = 1e18 + 42;
void win_dfs1()
{
for(auto it: sa1.top_sort)
for(auto v: it)
{
sa1.win[v] = sa2.sum - sa2.total[sa1.mex[v]];
sa1.win_cnt[v] = sa1.win[v];
for(auto it: sa1.to[v])
{
sa1.win_cnt[v] += sa1.win_cnt[it.second];
sa1.win_cnt[v] = min(sa1.win_cnt[v], inf);
}
}
}

void win_dfs2()
{
for(auto it: sa2.top_sort)
for(auto v: it)
{
sa2.win[v] = mex_ans != sa2.mex[v];
sa2.win_cnt[v] = sa2.win[v];
for(auto it: sa2.to[v])
sa2.win_cnt[v] += sa2.win_cnt[it.second];
}
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
int64_t k;
cin >> n >> m >> k;
string a, b;
cin >> a >> b;
sa1.build(a);
sa2.build(b);
win_dfs1();
if(k > sa1.win_cnt[0])
{
cout << "no solution" << endl;
return 0;
}
sa1.rec_dfs(0, k);
cout << ans << endl;
win_dfs2();
ans = "";
sa2.rec_dfs(0, k);
cout << ans << endl;
return 0;
}

In   Java  :

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;

public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";

static class Result
{
int[] sa;
int[] lcp;
int[][] branches;
long[] count;
int[] zero, one;
int[] deadline;

public Result(int[] sa, int[] lcp,
int[][] branches, long[] count,
int[] zero, int[] one, int[] deadline) {
this.sa = sa;
this.lcp = lcp;
this.branches = branches;
this.count = count;
this.zero = zero;
this.one = one;
this.deadline = deadline;
}
}

static void solve()
{
int n = ni(), m = ni();
long K = nl();
char[] a = ns(n);
char[] b = ns(m);

Result ra = go(a);
Result rb = go(b);
long[] ca = ra.count;
long[] cb = rb.count;
if(cb.length < ca.length){
cb = Arrays.copyOf(cb, ca.length);
}
long totcb = 0;
for(long v : cb)totcb += v;

Arrays.sort(ra.branches, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});

K--;

// ""
{
long lcount = totcb - cb[ra.branches[0][3]];
if(K < lcount){
int[] resb = kth(rb, K, ra.branches[0][3]);

out.println("");
out.println(new String(b, resb[0], resb[1]));
return;
}else{
K -= lcount;
}
}

int bp = 0;

bp++;
for(int i = 0;i < n;i++){

long lcount = 0;
lcount += ra.zero[i] * (totcb - cb[0]);
lcount += ra.one[i] * (totcb - cb[1]);
int obp = bp;
while(bp < ra.branches.length && ra.branches[bp][0] == i){
lcount += totcb - cb[ra.branches[bp][3]];
bp++;
}

if(K < lcount){

int[] row = new int[n-ra.sa[i]];
Arrays.fill(row, -1);
for(int j = obp;j < bp;j++){
row[ra.branches[j][2]-1] = ra.branches[j][3];
}
for(int j = n-ra.sa[i]-1;j >= ra.deadline[i]+1;j--){
if(row[j] == -1){
if(j == n-ra.sa[i]-1){
row[j] = 0;
}else{
row[j] = row[j+1] > 0 ? 0 : 1;
}
}
}

for(int j = ra.deadline[i]+1;j < n-ra.sa[i];j++){
long llcount = totcb - cb[row[j]];
if(K < llcount){

int[] resa = new int[]{ra.sa[i], j+1};
int[] resb = kth(rb, K, row[j]);

out.println(new String(a, resa[0], resa[1]));
out.println(new String(b, resb[0], resb[1]));
return;
}else{
K -= llcount;
}
}
}else{
K -= lcount;
}
}

out.println("no solution");
}

static int[] kth(Result rb, long K, int proh)
{
Arrays.sort(rb.branches, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});

if(rb.branches[0][3] != proh){
if(K == 0){
return new int[]{0, 0};
}else{
K--;
}
}

int n = rb.sa.length;
int bp = 1;
for(int i = 0;i < n;i++){
// row
long lcount = 0;
if(proh != 0)lcount += rb.zero[i];
if(proh != 1)lcount += rb.one[i];
int obp = bp;
while(bp < rb.branches.length && rb.branches[bp][0] == i){
if(proh != rb.branches[bp][3])lcount++;
bp++;
}
if(K < lcount){

int[] row = new int[n-rb.sa[i]];
Arrays.fill(row, -1);
for(int j = obp;j < bp;j++){
row[rb.branches[j][2]-1] = rb.branches[j][3];
}
for(int j = n-rb.sa[i]-1;
j >= rb.deadline[i]+1;j--){
if(row[j] == -1){
if(j == n-rb.sa[i]-1){
row[j] = 0;
}else{
row[j] = row[j+1] > 0 ? 0 : 1;
}
}
}

for(int j = rb.deadline[i]+1;
j < n-rb.sa[i];j++){
if(row[j] != proh){
if(K == 0){
return new int[]{rb.sa[i], j+1};
}
K--;
}
}
}else{
K -= lcount;
}
}
return null;
}

static Result go(char[] a)
{
int[] sa = suffixsort(a);
int[] lcp = buildLCP(a, sa);

int[][] branches = findBranches(lcp);

LResult lres = countNimber(sa, lcp, branches);

return new Result(sa, lcp, branches,
lres.count, lres.zero, lres.one, lres.deadline);
}

private static LResult countNimber(int[] sa,

int[] lcp, int[][] branches)
{
int n = sa.length;

int[] zero = new int[n];
int[] one = new int[n];
int[] deadline = new int[n];
Arrays.fill(deadline, -1);

int[] hs = new int[n];
int[] nim = new int[n];
Arrays.fill(nim, -1);
long[] count = new long[n+1];
for(int i = 0;i < n;i++){
hs[i] = n-sa[i]+1;
}
int[] alive = new int[n];
Arrays.fill(alive, 1);
int[] ftalive = buildFenwick(alive);
int bp = 0;
int[] bs2 = new int[n];
for(int[] branch : branches){
int sp = 0;
int L = branch[0];
int R = branch[1];
int h = branch[2];

if(L == -1)L = 0;
int bs = 0;

for(int i = L;i <= R && i >= 0;
i = after(ftalive, i)){

if(nim[i] >= 0)count[nim[i]]++;
int bet = hs[i]-h-1;

if(nim[i] == 0){
count[0] += bet / 2;
count[1] += (bet+1)/2;
zero[i] += bet/2;
one[i] += (bet+1)/2;
// 0|10|1
bs |= 1<<(bet&1);
}else{
count[0] += (bet+1) / 2;
count[1] += bet/2;
zero[i] += (bet+1)/2;
one[i] += bet/2;
if(bet == 0){
if(nim[i] >= 0){
if(nim[i] <= 31){
bs |= 1<<nim[i];
}else{
bs2[sp++] = nim[i];
}
}
}else{
bs |= 1<<((bet&1)^1);
}
}
hs[i] = h;

if(i > L){
// kill
alive[i] = 0;
deadline[i] = h-1;
addFenwick(ftalive, i, -1);
}
}

int clus = Integer.numberOfTrailingZeros(~bs);
if(clus >= 32){
Arrays.sort(bs2, 0, sp);
clus = 32;
for(int q = 0;q < sp;){
if(bs2[q] == clus){
while(q < sp && bs2[q] == clus)q++;
clus++;
}else{
break;
}
}
}

branches[bp++][3] = nim[L] = clus;
if(branch[0] == -1)count[nim[L]]++;
}

return new LResult(count, zero, one, deadline);
}

static class LResult
{
long[] count;
int[] zero, one;
int[] deadline;
public LResult(long[] count, int[] zero,
int[] one, int[] deadline) {
this.count = count;
this.zero = zero;
this.one = one;
this.deadline = deadline;
}
}

static int[][] findBranches(int[] a)
{
int n = a.length;
long[] ap = new long[n];
for(int i = 0;i < n;i++)ap[i] = (long)(1000000-a[i])<<32|i;
Arrays.sort(ap);
int[][] branches = new int[n][];

int p = 0;
int[] flag = new int[n];
Arrays.fill(flag, 1);
int[] ft = buildFenwick(flag);
for(int i = 0;i < n;i++){
int j;
int last = (int)ap[i];
int va = 1000000-(int)(ap[i]>>>32);
for(j = (int)ap[i];j >= 0 && j < n &&
flag[j] == 1 && a[j] >= va;j = after(ft, j)){
last = j;
flag[j] = 0;
addFenwick(ft, j, -1);
}

if(j == (int)ap[i])continue;

branches[p++] = new int[]
{before(ft, (int)ap[i]), last, va, -1};

}
return Arrays.copyOf(branches, p);
}

public static int sumFenwick(int[] ft, int i)
{
int sum = 0;
for(i++;i > 0;i -= i&-i)sum += ft[i];
return sum;
}

public static void addFenwick(int[] ft, int i, int v)
{
if(v == 0)return;
int n = ft.length;
for(i++;i < n;i += i&-i)ft[i] += v;
}

public static int findGFenwick(int[] ft, int v)
{
int i = 0;
int n = ft.length;
for(int b = Integer.highestOneBit(n);
b != 0 && i < n;b >>= 1){
if(i + b < n){
int t = i + b;
if(v >= ft[t]){
i = t;
v -= ft[t];
}
}
}
return v != 0 ? -(i+1) : i-1;
}

public static int valFenwick(int[] ft, int i)
{
return sumFenwick(ft, i) - sumFenwick(ft, i-1);
}

public static int[] restoreFenwick(int[] ft)
{
int n = ft.length-1;
int[] ret = new int[n];
for(int i = 0;i < n;i++)ret[i] = sumFenwick(ft, i);
for(int i = n-1;i >= 1;i--)ret[i] -= ret[i-1];
return ret;
}

public static int before(int[] ft, int x)
{
int u = sumFenwick(ft, x-1);
if(u == 0)return -1;
return findGFenwick(ft, u-1)+1;
}

public static int after(int[] ft, int x)
{
int u = sumFenwick(ft, x);
int f = findGFenwick(ft, u);
if(f+1 >= ft.length-1)return -1;
return f+1;
}

public static int[] buildFenwick(int[] a)
{
int n = a.length;
int[] ft = new int[n+1];
System.arraycopy(a, 0, ft, 1, n);
for(int k = 2, h = 1;k <= n;k*=2, h*=2){
for(int i = k;i <= n;i+=k){
ft[i] += ft[i-h];
}
}
return ft;
}

public static int[] buildLCP(char[] str, int[] sa)
{
int n = str.length;
int h = 0;
int[] lcp = new int[n];
int[] b = new int[n];
for(int i = 0;i < n;i++)b[sa[i]] = i;
for(int i = 0;i < n;i++){
if(b[i] > 0){
for(int j = sa[b[i]-1]; j+h<n &&
i+h<n && str[j+h] == str[i+h]; h++);
lcp[b[i]] = h;
}else{
lcp[b[i]] = 0;
}
if(h > 0)h--;
}
return lcp;
}

private static interface BaseArray {
public int get(int i);

public void set(int i, int val);

public int update(int i, int val);
}

private static class CharArray implements BaseArray {
private char[] m_A = null;
private int m_pos = 0;

CharArray(char[] A, int pos) {
m_A = A;
m_pos = pos;
}

public int get(int i) {
return m_A[m_pos + i] & 0xffff;
}

public void set(int i, int val) {
m_A[m_pos + i] = (char) (val & 0xffff);
}

public int update(int i, int val) {
return m_A[m_pos + i] += val & 0xffff;
}
}

private static class IntArray implements BaseArray {
private int[] m_A = null;
private int m_pos = 0;

IntArray(int[] A, int pos) {
m_A = A;
m_pos = pos;
}

public int get(int i) {
return m_A[m_pos + i];
}

public void set(int i, int val) {
m_A[m_pos + i] = val;
}

public int update(int i, int val) {
return m_A[m_pos + i] += val;
}
}

private static void getCounts(BaseArray T,
BaseArray C, int n, int k) {
int i;
for(i = 0;i < k;++i){
C.set(i, 0);
}
for(i = 0;i < n;++i){
C.update(T.get(i), 1);
}
}

private static void getBuckets(BaseArray C,
BaseArray B, int k, boolean end) {
int i, sum = 0;
if(end != false){
for(i = 0;i < k;++i){
sum += C.get(i);
B.set(i, sum);
}
}else{
for(i = 0;i < k;++i){
sum += C.get(i);
B.set(i, sum - C.get(i));
}
}
}

/* sort all type LMS suffixes */
private static void LMSsort(BaseArray T,
int[] SA, BaseArray C,
BaseArray B, int n, int k) {
int b, i, j;
int c0, c1;
/* compute SAl */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, false);
j = n - 1;
b = B.get(c1 = T.get(j));
--j;
SA[b++] = (T.get(j) < c1) ? ~j : j;
for(i = 0;i < n;++i){
if(0 < (j = SA[i])){
if((c0 = T.get(j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
--j;
SA[b++] = (T.get(j) < c1) ? ~j : j;
SA[i] = 0;
}else if(j < 0){
SA[i] = ~j;
}
}
/* compute SAs */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, true);
for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
if(0 < (j = SA[i])){
if((c0 = T.get(j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
--j;
SA[--b] = (T.get(j) > c1) ? ~(j + 1) : j;
SA[i] = 0;
}
}
}

private static int LMSpostproc(BaseArray T,
int[] SA, int n, int m) {
int i, j, p, q, plen, qlen, name;
int c0, c1;
boolean diff;

for(i = 0;(p = SA[i]) < 0;++i){
SA[i] = ~p;
}
if(i < m){
for(j = i, ++i;;++i){
if((p = SA[i]) < 0){
SA[j++] = ~p;
SA[i] = 0;
if(j == m){
break;
}
}
}
}

i = n - 1;
j = n - 1;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
SA[m + ((i + 1) >> 1)] = j - i;
j = i + 1;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}

for(i = 0, name = 0, q = n, qlen = 0;i < m;++i){
p = SA[i];
plen = SA[m + (p >> 1)];
diff = true;
if((plen == qlen) && ((q + plen) < n)){
for(j = 0;(j < plen) && (T.get(p + j) == T.get(q + j));++j){
}
if(j == plen){
diff = false;
}
}
if(diff != false){
++name;
q = p;
qlen = plen;
}
SA[m + (p >> 1)] = name;
}

return name;
}

private static void induceSA(BaseArray T, int[] SA,
BaseArray C,
BaseArray B, int n, int k) {
int b, i, j;
int c0, c1;
/* compute SAl */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, false);
j = n - 1;
b = B.get(c1 = T.get(j));
SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
for(i = 0;i < n;++i){
j = SA[i];
SA[i] = ~j;
if(0 < j){
if((c0 = T.get(--j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
}
}
/* compute SAs */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
if(0 < (j = SA[i])){
if((c0 = T.get(--j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
SA[--b] = ((j == 0) || (T.get(j - 1) > c1)) ? ~j : j;
}else{
SA[i] = ~j;
}
}
}

private static void SA_IS(BaseArray T, int[] SA, int fs, int n, int k) {
BaseArray C, B, RA;
int i, j, b, m, p, q, name, newfs;
int c0, c1;
int flags = 0;

if(k <= 256){
C = new IntArray(new int[k], 0);
if(k <= fs){
B = new IntArray(SA, n + fs - k);
flags = 1;
}else{
B = new IntArray(new int[k], 0);
flags = 3;
}
}else if(k <= fs){
C = new IntArray(SA, n + fs - k);
if(k <= (fs - k)){
B = new IntArray(SA, n + fs - k * 2);
flags = 0;
}else if(k <= 1024){
B = new IntArray(new int[k], 0);
flags = 2;
}else{
B = C;
flags = 8;
}
}else{
C = B = new IntArray(new int[k], 0);
flags = 4 | 8;
}

getCounts(T, C, n, k);
getBuckets(C, B, k, true);
for(i = 0;i < n;++i){
SA[i] = 0;
}
b = -1;
i = n - 1;
j = n;
m = 0;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
if(0 <= b){
SA[b] = j;
}
b = B.update(c1, -1);
j = i;
++m;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
if(1 < m){
LMSsort(T, SA, C, B, n, k);
name = LMSpostproc(T, SA, n, m);
}else if(m == 1){
SA[b] = j + 1;
name = 1;
}else{
name = 0;
}

if(name < m){
if((flags & 4) != 0){
C = null;
B = null;
}
if((flags & 2) != 0){
B = null;
}
newfs = (n + fs) - (m * 2);
if((flags & (1 | 4 | 8)) == 0){
if((k + name) <= newfs){
newfs -= k;
}else{
flags |= 8;
}
}
for(i = m + (n >> 1) - 1, j = m * 2 + newfs - 1;m <= i;--i){
if(SA[i] != 0){
SA[j--] = SA[i] - 1;
}
}
RA = new IntArray(SA, m + newfs);
SA_IS(RA, SA, newfs, m, name);
RA = null;

i = n - 1;
j = m * 2 - 1;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
SA[j--] = i + 1;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}

for(i = 0;i < m;++i){
SA[i] = SA[m + SA[i]];
}
if((flags & 4) != 0){
C = B = new IntArray(new int[k], 0);
}
if((flags & 2) != 0){
B = new IntArray(new int[k], 0);
}
}

if((flags & 8) != 0){
getCounts(T, C, n, k);
}

if(1 < m){
getBuckets(C, B, k, true);
i = m - 1;
j = n;
p = SA[m - 1];
c1 = T.get(p);
do{
q = B.get(c0 = c1);
while (q < j){
SA[--j] = 0;
}
do{
SA[--j] = p;
if(--i < 0){
break;
}
p = SA[i];
}while ((c1 = T.get(p)) == c0);
}while (0 <= i);
while (0 < j){
SA[--j] = 0;
}
}
induceSA(T, SA, C, B, n, k);
C = null;
B = null;
}

/* char */
public static int[] suffixsort(char[] T) {
if(T == null)return null;
int n = T.length;
int[] SA = new int[n];
if(n <= 1){
if(n == 1){
SA[0] = 0;
}
return SA;
}
SA_IS(new CharArray(T, 0), SA, 0, n, 65536);
return SA;
}

public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in :
new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);

solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}

private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))
return false;

try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}

private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;

private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); }
catch (IOException e)
{ throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}

private static boolean isSpaceChar(int c)
{ return !(c >= 33 && c <= 126); }
private static int skip()
{ int b;
while((b = readByte()) != -1 && isSpaceChar(b));
return b; }

private static double nd() { return Double.parseDouble(ns()); }
private static char nc()
{ return (char)skip(); }

private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b)))
{ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}

private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}

private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}

private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}

private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !(
(b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}

private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !(
(b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}

private static void tr(Object... o)
{ if(INPUT.length() != 0)
System.out.println(Arrays.deepToString(o)); }
}

In  C  :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define A_SIZE 26
#define MIN_C 'a'
typedef struct _st_node st_node;
typedef struct _st_edge st_edge;
struct _st_node{
int x;
unsigned long long count;
st_node *suffix_link;
st_edge *edges[A_SIZE+1];
};
struct _st_edge{
int from;
int to;
int suffix_index;
st_node *node;
};
int dfs0(st_node *root,int flag);
unsigned long long dfs1(st_node *root);
void dfs2(int idx,st_node *root);
unsigned long long dfs3(st_node *root);
void dfs4(int idx,st_node *root);
void suffix_tree(st_node *root,char *str,int len);
char a[300001],b[300001],ans[300001];
unsigned long long dp[50],total,K,KK,val;

int main(){
int N,M,i;
st_node r1,r2;
scanf("%d%d%lld%s%s",&N,&M,&K,a,b);
suffix_tree(&r1,a,N);
suffix_tree(&r2,b,M);
dfs0(&r1,0);
dfs0(&r2,1);
for(i=0;i<50;i++)
total+=dp[i];
dfs1(&r1);
if(r1.count<K){
printf("no solution\n");
return 0;
}
dfs2(0,&r1);
dfs3(&r2);
KK=0;
dfs4(0,&r2);
return 0;
}
int dfs0(st_node *root,int flag){
char arr[20];
int len,ret,i;
if(!root){
if(flag)
dp[0]++;
return 0;
}
memset(arr,0,sizeof(arr));
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
ret=dfs0(root->edges[i]->node,flag);
if(len==1)
arr[ret]=1;
else
if(ret){
if(flag){
dp[0]+=len/2;
dp[1]+=(len-1)/2;
}
if(len%2)
arr[1]=1;
else
arr[0]=1;
}
else{
if(flag){
dp[1]+=len/2;
dp[0]+=(len-1)/2;
}
if(len%2)
arr[0]=1;
else
arr[1]=1;
}
}
for(i=0;i<20 && arr[i];i++);
if(flag)
dp[i]++;
root->x=i;
return i;
}
unsigned long long dfs1(st_node *root){
int len,ret,i;
unsigned long long ret2,count=0;
if(!root)
return total-dp[0];
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
ret2=dfs1(root->edges[i]->node);
if(root->edges[i]->node)
ret=root->edges[i]->node->x;
else
ret=0;
count+=ret2;
if(ret){
count+=len/2*(total-dp[0]);
count+=(len-1)/2*(total-dp[1]);
}
else{
count+=len/2*(total-dp[1]);
count+=(len-1)/2*(total-dp[0]);
}
}
count+=total-dp[root->x];
root->count=count;
return count;
}
void dfs2(int idx,st_node *root){
int len,ret,start,i,j;
unsigned long long t1,t2;
if(!root){
ans[idx]=0;
printf("%s\n",ans);
val=0;
K-=KK;
return;
}
if(KK+total-dp[root->x]>=K){
ans[idx]=0;
printf("%s\n",ans);
val=root->x;
K-=KK;
return;
}
KK+=total-dp[root->x];
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
if(root->edges[i]->node){
ret=root->edges[i]->node->x;
t2=root->edges[i]->node->count;
}
else{
ret=0;
t2=total-dp[0];
}
t1=0;
if(ret){
t1+=len/2*(total-dp[0]);
t1+=(len-1)/2*(total-dp[1]);
}
else{
t1+=len/2*(total-dp[1]);
t1+=(len-1)/2*(total-dp[0]);
}
if(KK+t1+t2<K)
KK+=t1+t2;
else if(KK+t1<K){
KK+=t1;
for(j=root->edges[i]->from;j<=root->edges[i]->to;j++)
ans[idx+j-root->edges[i]->from]=a[j];
dfs2(idx+root->edges[
i]->to-root->edges[i]->from+1,root->edges[i]->node);
return;
}
else{
if((ret && len%2) || (!ret && len%2==0))
start=1;
else
start=0;
for(j=root->edges[
i]->from;j<root->edges[i]->to;j++,start^=1){
ans[idx+j-root->edges[i]->from]=a[j];
if(KK+total-dp[start]>=K){
ans[idx+j+1-root->edges[i]->from]=0;
printf("%s\n",ans);
val=start;
K-=KK;
return;
}
KK+=total-dp[start];
}
return;
}
}
return;
}
unsigned long long dfs3(st_node *root){
int len,ret,i;
unsigned long long ret2,count=0;
if(!root){
if(val)
return 1;
return 0;
}
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
ret2=dfs3(root->edges[i]->node);
if(root->edges[i]->node)
ret=root->edges[i]->node->x;
else
ret=0;
count+=ret2;
if(ret){
if(val!=0)
count+=len/2;
if(val!=1)
count+=(len-1)/2;
}
else{
if(val!=1)
count+=len/2;
if(val!=0)
count+=(len-1)/2;
}
}
if(val!=root->x)
count++;
root->count=count;
return count;
}
void dfs4(int idx,st_node *root){
int len,ret,start,i,j;
unsigned long long t1,t2;
if(!root){
ans[idx]=0;
printf("%s\n",ans);
return;
}
if(val!=root->x && KK+1==K){
ans[idx]=0;
printf("%s\n",ans);
return;
}
if(val!=root->x)
KK++;
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
if(root->edges[i]->node){
ret=root->edges[i]->node->x;
t2=root->edges[i]->node->count;
}
else{
ret=0;
if(val)
t2=1;
else
t2=0;
}
t1=0;
if(ret){
if(val!=0)
t1+=len/2;
if(val!=1)
t1+=(len-1)/2;
}
else{
if(val!=1)
t1+=len/2;
if(val!=0)
t1+=(len-1)/2;
}
if(KK+t1+t2<K)
KK+=t1+t2;
else if(KK+t1<K){
KK+=t1;
for(j=root->edges[
i]->from;j<=root->edges[i]->to;j++)
ans[idx+j-root->edges[i]->from]=b[j];
dfs4(idx+root->edges[
i]->to-root->edges[i]->from+1,root->edges[i]->node);
return;
}
else{
if((ret && len%2) || (!ret && len%2==0))
start=1;
else
start=0;
for(j=root->edges[i]->from;j<root->edges[i]->to;j++,start^=1){
ans[idx+j-root->edges[i]->from]=b[j];
if(val!=start){
if(KK+1==K){
ans[idx+j+1-root->edges[i]->from]=0;
printf("%s\n",ans);
return;
}
KK++;
}
}
return;
}
}
return;
}
void suffix_tree(st_node *root,char *str,int len){
int a_edge,a_len=0,remainder=0,need_insert,from,i;
st_node *a_node=root,*pre_node,*t_node;
st_edge *t_edge;
memset(root,0,sizeof(st_node));
for(i=0;i<len;i++){
need_insert=0;
pre_node=NULL;
remainder++;
if(i==len)
need_insert=1;
else if(a_len)
if(str[a_node->edges[
a_edge]->from+a_len]==str[i])
if(a_node->edges[
a_edge]->from+a_len==a_node->edges[a_edge]->to){
a_node=a_node->edges[a_edge]->node;
a_len=0;
}
else
a_len++;
else
need_insert=1;
else
if(a_node->edges[str[i]-MIN_C])
if(a_node->edges[
str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
a_node=a_node->edges[str[i]-MIN_C]->node;
else{
a_edge=str[i]-MIN_C;
a_len=1;
}
else
need_insert=1;
if(need_insert)
for(;remainder>0;remainder--){
if(!a_len)
if(i==len){
a_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
a_node->edges[A_SIZE]->suffix_index=i-remainder+1;
a_node->edges[A_SIZE]->node=NULL;
}
else{
if(a_node->edges[str[i]-MIN_C]){
if(pre_node)
pre_node->suffix_link=a_node;
if(a_node->edges[
str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
a_node=a_node->edges[str[i]-MIN_C]->node;
else{
a_edge=str[i]-MIN_C;
a_len=1;
}
break;
}
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=i;
t_edge->to=len-1;
t_edge->suffix_index=i-remainder+1;
t_edge->node=NULL;
a_node->edges[str[i]-MIN_C]=t_edge;
t_node=a_node;
}
else{
if(i!=len && str[a_node->edges[
a_edge]->from+a_len]==str[i]){
if(pre_node)
pre_node->suffix_link=a_node;
if(a_node->edges[a_edge]->from+a_len==a_node->edges[
a_edge]->to){
a_node=a_node->edges[a_edge]->node;
a_len=0;
}
else
a_len++;
break;
}
t_node=(st_node*)malloc(sizeof(st_node));
memset(t_node,0,sizeof(st_node));
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=a_node->edges[a_edge]->from+a_len;
t_edge->to=a_node->edges[a_edge]->to;
t_edge->suffix_index=a_node->edges[a_edge]->suffix_index;
t_edge->node=a_node->edges[a_edge]->node;
from=a_node->edges[a_edge]->from;
a_node->edges[a_edge]->node=t_node;
a_node->edges[a_edge]->to=a_node->edges[
a_edge]->from+a_len-1;
t_node->edges[str[t_edge->from]-MIN_C]=t_edge;
if(i==len){
t_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
t_node->edges[A_SIZE]->suffix_index=i-remainder+1;
t_node->edges[A_SIZE]->node=NULL;
}
else{
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=i;
t_edge->to=len-1;
t_edge->suffix_index=i-remainder+1;
t_edge->node=NULL;
t_node->edges[str[i]-MIN_C]=t_edge;
}
}
if(pre_node)
pre_node->suffix_link=t_node;
pre_node=t_node;
if(a_node==root && a_len>0){
if(remainder>1)
a_edge=str[i-remainder+2]-MIN_C;
from=i-remainder+2;
a_len--;
}
else if(a_node!=root)
if(a_node->suffix_link)
a_node=a_node->suffix_link;
else
a_node=root;
while(a_len>0 && a_len>=a_node->edges[
a_edge]->to-a_node->edges[a_edge]->from+1){
a_len-=a_node->edges[
a_edge]->to-a_node->edges[a_edge]->from+1;
from+=a_node->edges[
a_edge]->to-a_node->edges[a_edge]->from+1;
a_node=a_node->edges[a_edge]->node;
a_edge=str[from]-MIN_C;
}
}
}
return;
}```
```

## AND xor OR

Given an array of distinct elements. Let and be the smallest and the next smallest element in the interval where . . where , are the bitwise operators , and respectively. Your task is to find the maximum possible value of . Input Format First line contains integer N. Second line contains N integers, representing elements of the array A[] . Output Format Print the value

## Waiter

You are a waiter at a party. There is a pile of numbered plates. Create an empty answers array. At each iteration, i, remove each plate from the top of the stack in order. Determine if the number on the plate is evenly divisible ith the prime number. If it is, stack it in pile Bi. Otherwise, stack it in stack Ai. Store the values Bi in from top to bottom in answers. In the next iteration, do the

## Queue using Two Stacks

A queue is an abstract data type that maintains the order in which elements were added to it, allowing the oldest elements to be removed from the front and new elements to be added to the rear. This is called a First-In-First-Out (FIFO) data structure because the first element added to the queue (i.e., the one that has been waiting the longest) is always the first one to be removed. A basic que

## Castle on the Grid

You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):

## Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr