Video editorials for B, C, and D are available on ak2006's channel.
1844A - Subtraction Game
There exists a small $$$n$$$ where the second player can win.
If $$$a \ge 2$$$, then $$$n = 1$$$ works.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t,a,b;
scanf("%d",&t);
while (t--) {
scanf("%d %d",&a,&b);
printf("%d\n",a+b);
}
return 0;
}
1844B - Permutations & Primes
In order for $$$(l,r)$$$ to contribute to the primality, we must have $$$\operatorname{MEX}(a_l,\dots,a_r) \ge 2$$$, so there is some value $$$1$$$ between indices $$$l$$$ and $$$r$$$.
To maximize the number of pairs $$$(l,r)$$$ that contain the value $$$1$$$, we should put $$$1$$$ near the middle of the array.
To minimize the number of pairs $$$(l,r)$$$ where $$$\operatorname{MEX}(a_l,\dots,a_r) \ge 2$$$ but is not prime, we should put $$$2$$$ and $$$3$$$ at the ends of the array.
#include <bits/stdc++.h>
using namespace std;
int a[200000];
int main() {
int i;
int t,n;
scanf("%d",&t);
while (t--) {
scanf("%d",&n);
if (n == 1) printf("1\n");
else if (n == 2) printf("1 2\n");
else {
int c = 4;
fill(a,a+n,0);
a[0] = 2,a[n/2] = 1,a[n-1] = 3;
for (i = 0; i < n; i++) {
if (a[i] == 0) a[i] = c++;
}
for (i = 0; i < n; i++) printf("%d%c",a[i],(i == n-1) ? '\n':' ');
}
}
return 0;
}
1844C - Particles
The answer is the sum of some subset of $$$c_1,\dots,c_n$$$. Think about which subsets are obtainable.
Consider the set of even-indexed particles and the set of odd-indexed particles.
#include <bits/stdc++.h>
using namespace std;
typedef long long int LLI;
int c[200000];
int main() {
int i;
int t,n;
scanf("%d",&t);
while (t--) {
scanf("%d",&n);
for (i = 0; i < n; i++) scanf("%d",&c[i]);
int allneg = 1;
for (i = 0; i < n; i++) allneg &= (c[i] < 0);
if (allneg) printf("%d\n",*max_element(c,c+n));
else {
LLI ans1 = 0,ans2 = 0;
for (i = 0; i < n; i++) {
if (i & 1) ans1 += max(c[i],0);
else ans2 += max(c[i],0);
}
printf("%lld\n",max(ans1,ans2));
}
}
return 0;
}
1844D - Row Major
Describe, using a graph, all the pairs of characters in $$$s$$$ that need to be different.
Consider the smallest positive integer that does not divide $$$n$$$.
#include <bits/stdc++.h>
using namespace std;
char s[1000001];
int main() {
int i;
int t,n;
scanf("%d",&t);
while (t--) {
scanf("%d",&n);
int c = 1;
while ((n % c) == 0) c++;
for (i = 0; i < n; i++) s[i] = 'a'+(i % c);
s[n] = '\0';
printf("%s\n",s);
}
return 0;
}
1844E - Great Grids
Try to find a characterization of all great grids.
There are two approaches that lead to the same conclusion. Approach 1 is more clever and leads more easily to the conclusion, while approach 2 is perhaps more natural to consider. Feel free to read the hint towards the approach that sounds better.
Think of the letters as numbers modulo $$$3$$$ and look at differences of adjacent cells.
Draw a / or \ for each $$$2 \times 2$$$ subgrid connecting the equal letters, and look for patterns.
In either approach, we can associate a type to each row and column, which has one of two possibilities. The constraints correspond to a row and a column needing to have the same or different types.
The problem reduces to checking the $$$2$$$-colourability of a graph.
#include <bits/stdc++.h>
using namespace std;
typedef vector<pair<int,int> > vpii;
#define mp make_pair
#define pb push_back
vpii adjList[4000];
int colour[4000],bad = 0;
int doDFS(int u,int c) {
if (colour[u] != -1) {
if (colour[u] != c) bad = 1;
return 0;
}
colour[u] = c;
for (auto [v,e]: adjList[u]) doDFS(v,c^e);
return 0;
}
int main() {
int i;
int t,n,m,k;
int x1,y1,x2,y2;
scanf("%d",&t);
while (t--) {
scanf("%d %d %d",&n,&m,&k);
for (i = 0; i < k; i++) {
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
x1--,y1--,x2--,y2--;
adjList[min(x1,x2)].pb(mp(n+min(y1,y2),(x1+y1 != x2+y2)));
adjList[n+min(y1,y2)].pb(mp(min(x1,x2),(x1+y1 != x2+y2)));
}
fill(colour,colour+n+m,-1),bad = 0;
for (i = 0; i < n+m; i++) {
if (colour[i] == -1) doDFS(i,0);
}
printf(bad ? "NO\n":"YES\n");
for (i = 0; i < n+m; i++) adjList[i].clear();
}
return 0;
}
1844F1 - Min Cost Permutation (Easy Version)
Solve the case $$$c \ge 0$$$ first. There is a very simple description of the answer.
What is the answer when $$$c = 0$$$?
When $$$c \ge 0$$$, the answer is the array sorted in nondecreasing order.
When $$$c < 0$$$, the minimum cost is achieved by sorting the array in nonincreasing order, but this is not the lexicographically smallest. Try to greedily form the lexicographically smallest array one element at a time.
#include <bits/stdc++.h>
using namespace std;
typedef long long int LLI;
int a[200000];
int main() {
int i,j;
int t,n,c;
scanf("%d",&t);
while (t--) {
scanf("%d %d",&n,&c);
for (i = 0; i < n; i++) scanf("%d",&a[i]);
if (c >= 0) {
sort(a,a+n);
for (i = 0; i < n; i++) printf("%d%c",a[i],(i == n-1) ? '\n':' ');
continue;
}
sort(a,a+n,greater<int>());
for (i = 0; i < n; i++) {
for (j = n-1; j > i; j--) {
LLI diff = -abs(a[j]-a[j-1]-c);
if (j < n-1) {
diff -= abs(a[j+1]-a[j]-c);
diff += abs(a[j+1]-a[j-1]-c);
}
if (i == 0) diff += abs(a[i]-a[j]-c);
else {
diff -= abs(a[i]-a[i-1]-c);
diff += abs(a[i]-a[j]-c);
diff += abs(a[j]-a[i-1]-c);
}
if (diff == 0) {
for (; j > i; j--) swap(a[j],a[j-1]);
}
}
}
for (i = 0; i < n; i++) printf("%d%c",a[i],(i == n-1) ? '\n':' ');
}
return 0;
}
1844F2 - Min Cost Permutation (Hard Version)
These hints and solution continue from the solution for the easy version, so please read the solution for the easy version first.
We need to optimize the $$$\mathcal{O}(n^2)$$$ greedy with some data structures. There exist solutions with varying levels of data structure implementation depending on how much effort is put into characterizing the answer array. For a short solution, start by simplifying the formula $$$(*)$$$ (in the solution for the easy version) to get a cleaner description.
The condition is actually equivalent to ($$$a_{i-1}-a_{i+1} \le |c|$$$ or $$$a_{i-1} = a_i$$$ or $$$a_i = a_{i+1}$$$) and ($$$b_{k-1}-a_i \le |c|$$$).
Maintain a linked list of the unused entries of $$$a$$$ and a set of unused entries that satisfy ($$$a_{i-1}-a_{i+1} \le |c|$$$ or $$$a_{i-1} = a_i$$$ or $$$a_i = a_{i+1}$$$).
1844F2 - Min Cost Permutation (Hard Version)
Let $$$c < 0$$$.
We now simplify condition $$$(*)$$$, which involves considering a few cases depending on the sign of the terms. It turns out that the condition is equivalent to ($$$a_{i-1}-a_{i+1} \le |c|$$$ or $$$a_{i-1} = a_i$$$ or $$$a_i = a_{i+1}$$$) and ($$$b_{k-1}-a_i \le |c|$$$) (for full details, see the overall proof below).
Sort $$$a$$$ in nonincreasing order so that $$$a_1 \ge a_2 \ge \dots \ge a_n$$$. We can simulate the greedy algorithm from the easy version with the help of a linked list of the unused elements of $$$a$$$ and a set of $$$a_i$$$ which satisfy the first part of the condition, ($$$a_{i-1}-a_{i+1} \le |c|$$$ or $$$a_{i-1} = a_i$$$ or $$$a_i = a_{i+1}$$$). Here, $$$a_{i-1}$$$ and $$$a_{i+1}$$$ actually refer to the closest unused elements of $$$a$$$, which are $$$a_i$$$'s left and right pointers in the linked list, respectively.
Each time, we query the set for its smallest element $$$a_i$$$ that satisfies $$$a_i \ge b_{k-1}-|c|$$$. If this element does not exist, then we take $$$a_i$$$ to be the largest element in the linked list. Then, we set $$$b_k := a_i$$$, delete $$$a_i$$$ from the linked list, and update the set with the left and right elements of $$$a_i$$$ if they now satisfy the condition.
One small observation is that in the answer $$$b$$$, $$$b_1 = a_1$$$ and $$$b_n = a_n$$$. This may simplify the implementation since it means that some edge cases of $$$(*)$$$ actually don't need to be checked. It is also actually not necessary to check the $$$a_{i-1} = a_i$$$ or $$$a_i = a_{i+1}$$$ condition.
The time complexity is $$$\mathcal{O}(n \log n)$$$.
The case $$$n \le 2$$$ is trivial. In the following, we only consider the case $$$c < 0$$$ and $$$n \ge 3$$$. The case $$$c \ge 0$$$ follows by symmetry (reverse the array).
Let $$$c' := -c$$$ to reduce confusion with negative signs, and WLOG let $$$a_1 \ge a_2 \ge \dots \ge a_n$$$.
Instead of considering $$$\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$, consider a permutation $$$b$$$ that minimizes the augmented cost $$$|b_1-b_n-c|+\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$. By circular symmetry, WLOG rotate $$$b$$$ so that $$$b_n = a_n$$$.
We will perform a sequence of steps to sort $$$b$$$ in nonincreasing order without ever increasing the augmented cost. Consider looking at $$$b_{n-1},b_{n-2},\dots,b_1$$$ in order, such that when we look at $$$b_k$$$, we have the invariant that $$$b_{k+1} \ge b_{k+2} \ge \dots \ge b_n = a_n$$$. If $$$b_k \ge b_{k+1}$$$, do not do anything. Otherwise, since $$$b_k \ge a_n = b_n$$$, there exists an index $$$k+1 \le i < n$$$ such that $$$b_i \ge b_k \ge b_{i+1}$$$. Consider deleting $$$b_k$$$ from the array and reinserting it between index $$$i$$$ and $$$i+1$$$. We have the following results:
Claim 1: Deleting $$$b_k$$$ decreases the augmented cost by at least $$$c'$$$.
Proof: Let $$$x := b_{k-1}-b_k$$$ (or $$$b_n-b_1$$$ if $$$k = 1$$$) and $$$y := b_{k+1}-b_k \ge 0$$$. We need to check that $$$|x-y-c'|+c' \le |x-c'|+|-y-c'|$$$, which follows from $$$|x-c'|+|-y-c'| = |x-c'|+y+c' \ge |x-y-c'|+c'$$$ (we use the triangle inequality in the last step).
Note that equality holds if and only if $$$x-c' \le 0$$$, i.e. $$$b_{k-1}-b_k \le c'$$$.
Claim 2: Reinserting $$$b_k$$$ increases the augmented cost by at most $$$c'$$$.
Proof: Let $$$x := b_i-b_k \ge 0$$$ and $$$y := b_k-b_{i+1} \ge 0$$$. We need to check that $$$|x-c'|+|y-c'| \le |x+y-c'|+c'$$$. Consider four cases:
- If $$$x,y \ge c'$$$, then $$$|x-c'|+|y-c'| = x+y-2c' < (x+y-c')+c' = |x+y-c'|+c'$$$.
- If $$$x \ge c', y \le c'$$$, then $$$|x-c'|+|y-c'| = x-y \le (x+y-c')+c' = |x+y-c'|+c'$$$.
- If $$$x \le c', y \ge c'$$$, then $$$|x-c'|+|y-c'| = y-x \le (x+y-c')+c' = |x+y-c'|+c'$$$.
- If $$$x,y \le c'$$$, then $$$|x-c'|+|y-c'| = 2c'-x-y = (c'-x-y)+c' \le |x+y-c'|+c'$$$.
Note that equality holds if and only if $$$x = 0$$$ or $$$y = 0$$$ or $$$c'-x-y \ge 0$$$, i.e. $$$b_i-b_{i+1} \le c'$$$ or $$$b_i = b_k$$$ or $$$b_k = b_{i+1}$$$.
Therefore, each step does not increase the augmented cost. After all the steps, $$$b$$$ will be sorted in nonincreasing order. Therefore, the smallest possible augmented cost is $$$|a_1-a_n-c|+\sum_{i=1}^{n-1} |a_{i+1}-a_i-c|$$$.
Now note that $$$|a_1-a_n-c| = (a_1-a_n)+c'$$$ is the maximum possible value of $$$|b_1-b_n-c|$$$! This means that the minimum cost cannot be less than the minimum augmented cost minus $$$(a_1-a_n)+c'$$$. It follows that the minimum cost is obtained by sorting $$$a$$$ in nonincreasing order, and furthermore, any optimal permutation $$$b$$$ satisfies $$$b_1 = a_1$$$ and $$$b_n = a_n$$$.
Furthermore, suppose we have fixed $$$b_1,\dots,b_k$$$ and also $$$b_n = a_n$$$. By a similar argument (looking at $$$b_{n-1},\dots,b_{k+1}$$$ and reinserting them to the right), one optimal permutation $$$b_{k+1},\dots,b_n$$$ of the remaining elements is to sort them in nonincreasing order. Our greedy algorithm can only reach states where the optimal remaining permutation satisfies $$$b_n = a_n$$$, so it is correct.
Note that condition $$$(*)$$$ is similar to equality being achieved in both claim 1 and claim 2. It follows that $$$(*)$$$ is equivalent to ($$$a_{i-1}-a_{i+1} \le |c|$$$ or $$$a_{i-1} = a_i$$$ or $$$a_i = a_{i+1}$$$) and ($$$b_{k-1}-a_i \le |c|$$$) as claimed.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define mp make_pair
int a[200000],b[200000],l[200000],r[200000];
set<pii> S;
int main() {
int i;
int t,n,c;
scanf("%d",&t);
while (t--) {
scanf("%d %d",&n,&c);
for (i = 0; i < n; i++) scanf("%d",&a[i]);
if (c >= 0) {
sort(a,a+n);
for (i = 0; i < n; i++) printf("%d%c",a[i],(i == n-1) ? '\n':' ');
continue;
}
sort(a,a+n,greater<int>());
b[0] = a[0];
for (i = 0; i < n; i++) l[i] = (i+n-1) % n,r[i] = (i+1) % n;
for (i = 2; i < n-1; i++) {
if (a[l[i]]-a[r[i]] <= -c) S.insert(mp(a[i],i));
}
for (i = 1; i < n; i++) {
int u;
auto it = S.lower_bound(mp(b[i-1]+c,0));
if (it == S.end()) u = r[0];
else u = it->second,S.erase(it);
b[i] = a[u];
int x = l[u],y = r[u];
r[x] = y,l[y] = x;
S.erase(mp(a[x],x)),S.erase(mp(a[y],y));
if ((x != 0) && (l[x] != 0) && (r[x] != 0) && (a[l[x]]-a[r[x]] <= -c)) S.insert(mp(a[x],x));
if ((y != 0) && (l[y] != 0) && (r[y] != 0) && (a[l[y]]-a[r[y]] <= -c)) S.insert(mp(a[y],y));
}
for (i = 0; i < n; i++) printf("%d%c",b[i],(i == n-1) ? '\n':' ');
}
return 0;
}
1844G - Tree Weights
Model the problem as a system of linear equations.
Let $$$x_u$$$ be the sum of the weights of the edges on the path from node $$$1$$$ to node $$$u$$$. The equations are of the form $$$x_i + x_{i+1} - 2x_{\text{lca}(i,i+1)} = d_i$$$.
The intended solution does not do anything like attempt to maintain paths/virtual trees of known weight. One easily overlooked detail that is essential to the solution is that $$$x_i$$$ are integers.
Solve the equations modulo $$$2$$$ first, so that the $$$2x_{\text{lca}(i,i+1)}$$$ term disappears.
After solving the equations modulo $$$2$$$, we can similarly solve modulo $$$4$$$, $$$8$$$, etc.
#include <bits/stdc++.h>
using namespace std;
typedef long long int LLI;
typedef vector<pair<int,int> > vpii;
#define mp make_pair
#define pb push_back
vpii adjList[100000];
LLI d[100000];
int parent[100000][17],parenti[100000],depth[100000];
int doDFS(int u,int p,int d) {
parent[u][0] = p,depth[u] = d;
for (auto [v,i]: adjList[u]) {
if (v != p) parenti[v] = i,doDFS(v,u,d+1);
}
return 0;
}
int logn;
int lca(int u,int v) {
int i;
if (depth[u] < depth[v]) swap(u,v);
for (i = logn-1; i >= 0; i--) {
if ((parent[u][i] != -1) && (depth[parent[u][i]] >= depth[v])) u = parent[u][i];
}
if (u == v) return u;
for (i = logn-1; i >= 0; i--) {
if (parent[u][i] != parent[v][i]) u = parent[u][i],v = parent[v][i];
}
return parent[u][0];
}
int lcas[100000],bit[100000];
LLI ans[100000],w[100000];
int main() {
int i;
int n,u,v;
scanf("%d",&n);
for (i = 0; i < n-1; i++) {
scanf("%d %d",&u,&v);
u--,v--;
adjList[u].pb(mp(v,i));
adjList[v].pb(mp(u,i));
}
for (i = 0; i < n-1; i++) scanf("%lld",&d[i]);
int j;
doDFS(0,-1,0);
for (i = 1; (1 << i) < n; i++) {
for (j = 0; j < n; j++) {
if (parent[j][i-1] != -1) parent[j][i] = parent[parent[j][i-1]][i-1];
else parent[j][i] = -1;
}
}
logn = i;
for (i = 0; i < n-1; i++) lcas[i] = lca(i,i+1);
for (i = 0; i < 57; i++) {
bit[0] = 0;
for (j = 0; j < n-1; j++) bit[j+1] = bit[j]^(d[j] & 1);
for (j = 0; j < n-1; j++) d[j] = (d[j]-bit[j]-bit[j+1]+2*bit[lcas[j]])/2;
for (j = 0; j < n; j++) ans[j] |= ((LLI) bit[j] << i);
}
for (i = 0; i < n-1; i++) {
if (d[i] != 0) {
printf("-1\n");
return 0;
}
}
for (i = 1; i < n; i++) {
w[parenti[i]] = ans[i]-ans[parent[i][0]];
if (w[parenti[i]] <= 0) {
printf("-1\n");
return 0;
}
}
for (i = 0; i < n-1; i++) printf("%lld\n",w[i]);
return 0;
}
1844H - Multiple of Three Cycles
The partially formed permutation is composed of several paths and cycles. Only the length of each path/cycle modulo $$$3$$$ matters.
The problem reduces to the following: Given $$$a$$$ $$$1$$$s, $$$b$$$ $$$2$$$s, and $$$c$$$ $$$0$$$s, how many ways are there to build a permutation on these objects so that each cycle sums to a multiple of $$$3$$$? Let $$$f(a,b,c)$$$ be the answer. Write some dynamic programming recurrences for $$$f(a,b,c)$$$.
Note that $$$f(a,b,c) = (a+b+c)f(a,b,c-1)$$$ (choose the next object of any $$$0$$$ and merge them).
This allows us to eliminate the $$$c$$$ parameter, multiplying the answer by a factorial and inverse factorial.
Let $$$f(a,b) = f(a,b,0)$$$. Write down not one, but two recurrence relations $$$f(a,b)$$$ satisfies.
We have $$$f(a,b) = b(a+b-1)f(a-1,b-1) + (a-1)f(a-2,b+1)$$$ when $$$a > 0$$$ (choose the next object of any $$$1$$$ and merge them) and also $$$f(a,b) = a(a+b-1)f(a-1,b-1) + (b-1)f(a+1,b-2)$$$ when $$$b > 0$$$ (choose the next object of any $$$2$$$ and merge them).
These recurrences mean that given any two of $$$f(a,b),f(a-1,b-1),f(a+2,b-1),f(a-1,b+2)$$$, we can solve for the other two.
Consider the pairs $$$(a,b)$$$ that arise from the $$$n$$$ queries. These pairs can be visualized as a walk in the plane, where each each pair does not differ from the previous pair by much. If we carefully use the recurrences to solve for values of $$$f(a,b)$$$ from values we already know, we can answer all queries on this walk while calculating only $$$\mathcal{O}(n)$$$ values of $$$f(a,b)$$$.
#include <bits/stdc++.h>
using namespace std;
typedef long long int LLI;
#define MOD 998244353
int parent[300000],siz[300000];
int find(int n) {
if (parent[n] != n) parent[n] = find(parent[n]);
return parent[n];
}
int queries[600000][3],ans[600000];
int fact[300000],invfact[300000],invn[300000];
int inv(int n) {
int e = MOD-2,r = 1;
while (e > 0) {
if (e & 1) r = ((LLI) r*n) % MOD;
e >>= 1;
n = ((LLI) n*n) % MOD;
}
return r;
}
int main() {
int i;
int n,x,y,bad = 1e9;
int num[3];
scanf("%d",&n);
for (i = 0; i < n; i++) parent[i] = i,siz[i] = 1;
num[0] = 0,num[1] = n,num[2] = 0;
for (i = 0; i < n; i++) {
scanf("%d %d",&x,&y);
x--,y--;
if (find(x) != find(y)) {
num[siz[find(x)] % 3]--;
num[siz[find(y)] % 3]--;
siz[find(y)] += siz[find(x)];
parent[find(x)] = find(y);
num[siz[find(y)] % 3]++;
}
else if ((siz[find(x)] % 3) == 0) num[0]--;
else if (bad == 1e9) bad = i;
copy(num,num+3,queries[i]);
}
fact[0] = 1;
for (i = 1; i < n; i++) fact[i] = ((LLI) i*fact[i-1]) % MOD;
invfact[n-1] = inv(fact[n-1]);
for (i = n-2; i >= 0; i--) invfact[i] = ((LLI) (i+1)*invfact[i+1]) % MOD;
for (i = 1; i < n; i++) invn[i] = ((LLI) invfact[i]*fact[i-1]) % MOD;
int m = n;
while (num[1]+num[2] > 0) {
int a = (num[1] > 0) ? 1:2;
num[a]--;
int b = (num[1] > 0) ? 1:2;
num[b]--;
num[(a+b) % 3]++;
copy(num,num+3,queries[m++]);
}
x = 1,y = 1;
int u = 1,v = 8;
auto f = [&]() {
assert(x > 0);
int nu = (((v-(((LLI) (y+1)*(x+y+1)) % MOD)*u) % MOD)*invn[x]) % MOD;
int nv = ((((LLI) x*(x+y+2)) % MOD)*nu+(LLI) (y+2)*v) % MOD;
x--,y += 2,u = nu,v = nv;
if (u < 0) u += MOD;
if (v < 0) v += MOD;
};
auto g = [&]() {
assert(y > 0);
int nu = (((v-(((LLI) (x+1)*(x+y+1)) % MOD)*u) % MOD)*invn[y]) % MOD;
int nv = ((((LLI) y*(x+y+2)) % MOD)*nu+(LLI) (x+2)*v) % MOD;
x += 2,y--,u = nu,v = nv;
if (u < 0) u += MOD;
if (v < 0) v += MOD;
};
for (i = m-1; i >= 0; i--) {
int a = queries[i][1],b = queries[i][2],c = queries[i][0];
if ((a == 0) && (b == 0)) ans[i] = 1;
else if ((a == x) && (b == y)) ans[i] = u;
else if ((a == x-1) && (b == y+2)) f(),ans[i] = u;
else if ((a == x+2) && (b == y-1)) g(),ans[i] = u;
else if ((a == x+1) && (b == y+1)) {
if (x > 0) f(),g(),ans[i] = u;
else g(),f(),ans[i] = u;
}
else assert(0);
ans[i] = ((LLI) ans[i]*fact[a+b+c]) % MOD;
ans[i] = ((LLI) ans[i]*invfact[a+b]) % MOD;
}
for (i = 0; i < n; i++) printf("%d\n",(i >= bad) ? 0:ans[i]);
return 0;
}
