TheForces Round #23 (Balanced-Forces)
A. Coins
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have $$$a$$$ coins with a value of $$$1$$$,$$$b$$$ coins with a value of $$$10$$$ and $$$c$$$ coins with a value of $$$100$$$.

Determine if it possible to combine these coins to create a value of exactly $$$n$$$?

Input

The first line contains a positive integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.

The only line for each test case contains four integers $$$a,b,c,n$$$ $$$(0 \leq a,b,c,n \leq 10^9)$$$.

Output

For each test case, output YES if it is possible to combine these coins to create a value of exactly $$$n$$$.Otherwise,output NO.

Example
Input
4
0 0 0 0
10 9 1 201
12 9 1 201
18 8 1000000000 999
Output
YES
NO
YES
NO

B. Two Arrays Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob have two arrays $$$a,b$$$ of size $$$n$$$ where $$$a_n=b_n$$$.One day,they want to play a game and make a chessboard with $$$2n-1$$$ squares,each with a number (as shown in the following picture) .

Alice has a score $$$s_a$$$ and Bob has a score $$$s_b$$$.At the beginning,$$$s_a$$$ and $$$s_b$$$ are both $$$0$$$.

At the beginning of the game,Alice choose an index $$$i_a(1 \leq i_a \leq n)$$$.After knowing $$$i_a$$$,Bob choose an index $$$i_b(1 \leq i_b \leq n)$$$.And then,Alice and Bob take turns doing some operations, with Alice starting first.

In each turn:

  • if this turn is Alice's,let $$$s_a$$$ increase the number on the grid corresponding to $$$a_{i_a}$$$ and set the number on this grid to $$$0$$$;
  • if this turn is Bob's,let $$$s_b$$$ increase the number on the grid corresponding to $$$b_{i_b}$$$ and set the number on this grid to $$$0$$$;
  • After increasing the score, if the current player's index is less than $$$n$$$, increase the index by $$$1$$$. Otherwise, the current player "stays in place"(do not change the index).

When both players "stay in place", the game ends.

Alice wants to maximize $$$(s_a-s_b)$$$ and Bob wants to minimize $$$(s_a-s_b)$$$.Assuming they all take the best strategy, what is the final value of $$$(s_a-s_b)$$$?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

The third line of each testcase contains $$$n$$$ integers $$$b_1,b_2,...,b_n$$$ ($$$1 \leq b_i \leq 10^9$$$,$$$b_n=a_n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Example
Input
3
2
4 1
3 1
2
4 10
3 10
4
1 9 4 5
2 4 3 5
Output
2
7
5
Note

Test case $$$1$$$:

The chessboard is shown in the following picture:

First,Alice chooses $$$i_a=1$$$.After that,Bob chooses $$$i_b=1$$$.

In the first turn,the number on the grid corresponding to $$$a_{i_a}=a_1$$$ is $$$4$$$ .Alice makes $$$s_a$$$ increase by $$$4$$$,sets the number on the grid to $$$0$$$,and increases $$$i_a$$$ by $$$1$$$;

In the second turn,the number on the grid corresponding to $$$b_{i_b}=b_1$$$ is $$$3$$$.Bob makes $$$s_b$$$ increase by $$$3$$$,sets the number on the grid to $$$0$$$,and increases $$$i_b$$$ by $$$1$$$;

In the third turn,the number on the grid corresponding to $$$a_{i_a}=a_2$$$ is $$$1$$$.Alice makes $$$s_a$$$ increase by $$$1$$$,sets the number on the grid to $$$0$$$,and stays in place;

In the fourth turn,the number on the grid corresponding to $$$b_{i_b}=b_2$$$ is already $$$0$$$.Bob makes $$$s_b$$$ increase by $$$0$$$,sets the number on the grid to $$$0$$$,and stays in place.

The final value of $$$s_a-s_b=(4+1)-3=2$$$.It can be proven that they all take the best strategy.

Test case $$$2$$$:

Alice chooses $$$i_a=2$$$ and Bob chooses $$$i_b=1$$$.

C. Super Palindrome
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For a binary string $$$x$$$ of length $$$l(l \geq 3)$$$,we call $$$x$$$ super palindrome iff $$$x_1x_2...x_l$$$ is a palindrome and $$$x_1x_2...x_{l-2}$$$ is also a palindrome.

For example,111 and 010 are super palindromes but 1001,10100,11 are not.

You're given a binary string $$$s$$$ of length $$$n$$$.Count the number of substrings which are super palindromes in $$$s$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$($$$3 \le n \le 4 \cdot 10^5$$$).

The second line of each test case contains the binary string $$$s$$$ of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$4 \cdot10^5$$$.

Output

For each test case, print the number of substrings which are super palindromes in $$$s$$$.

Example
Input
2
6
000010
16
0110101001111101
Output
4
13
Note

Test Case $$$1$$$:

There're $$$4$$$ substrings which are super palindromes — $$$s_1s_2s_3,s_2s_3s_4,s_1s_2s_3s_4,s_4s_5s_6$$$.

D. Balanced Permutation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a positive integer $$$n$$$. Call a permutation $$$p$$$ of length $$$k$$$ balanced if there exist an integer $$$x$$$ $$$(1 \leq x \lt k)$$$ such that $$$p_1 + p_2 + \dots + p_x = p_{x+1} + p_{x+2} + \dots + p_k$$$.

Find the lexicographically smallest balanced permutation of length $$$n$$$.

A permutation of length $$$n$$$ is an array that contains $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in an arbitrary order. For example, $$$\{2,5,3,1,4\}$$$ is a permutation of length $$$5$$$, while $$$\{1,2,2\}$$$ and $$$\{1,3,4\}$$$ are not permutations of length $$$3$$$.

A permutation $$$p$$$ is lexicographically smaller than a permutation $$$q$$$ of the same length if $$$p_a \lt q_a$$$ where $$$a$$$ is the smallest integer such that $$$1 \leq a \leq |p|$$$ and $$$p_a \neq q_a$$$. For example, $$$\{1,2,3,4\}$$$ is lexicographically smaller than $$$\{1,4,2,3\}$$$ since $$$a = 2$$$ and $$$p_2 = 2 \lt 4 = q_2$$$.

Input

The first line contains a positive integer $$$t$$$ ($$$1 \leq t \leq 300$$$) — the number of test cases.

The only line for each test case contains an integer $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — the length of the permutation. It is guaranteed that $$$n$$$ is chosen in such a way that there always exists at least one balanced permutation of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a line containing $$$n$$$ integers $$$p_1,p_2,\dots,p_n$$$ — the lexicographically smallest balanced permutation.

Example
Input
4
3
4
7
8
Output
1 2 3 
1 4 2 3 
1 2 4 7 3 5 6 
1 2 3 4 8 5 6 7
Note

For the first test case, the permutation $$$\{1,2,3\}$$$ is balanced, since $$$p_1 + p_2 = p_3$$$. Since this is also the lexicographically smallest permutation of length $$$3$$$, the lexicographically smallest balanced permutation of length $$$3$$$ is $$$\{1,2,3\}$$$.

For the second test case, it can be proven that $$$\{1,2,3,4\},\{1,2,4,3\},\{1,3,2,4\},\{1,3,4,2\}$$$ are all not balanced. It can also be proven that $$$\{1,4,2,3\}$$$ is balanced.

E1. Magic Xor(Easy Version)
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is a easy version of this problem.The only difference is $$$k=2$$$ in this version.

You are given a binary array $$$a$$$ of size $$$n$$$ consisting of $$$0$$$ or $$$1$$$.

You can do the following operation any number of times:

  • choose an index $$$i$$$ ($$$1 \lt i \lt n$$$);
  • change $$$a_{i-1}$$$ to $$$a_{i-1}\oplus a_i$$$ and change $$$a_{i+1}$$$ to $$$a_{i+1}\oplus a_i$$$. (Here $$$\oplus$$$ donates the bitwise XOR).

Your goal is to make $$$a$$$ satisfy the following condition:

  • there are at most $$$k$$$ indices $$$i$$$ ($$$1\leq i \leq n$$$) satisfying $$$a_i=1$$$.

Find the minimum number of operations you need. It can be proven that your goal is always able to be realized.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1\le t\le 10^5$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $$$n,k$$$ ($$$4\le n\le 5\cdot 10^5,k=2$$$).

Then one line follows, containing $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$0\le a_i\le 1$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

Output

For each test case, output a single line — the minimum number of operations.

Example
Input
5
4 2
0 0 0 0
6 2
1 1 0 0 1 1
8 2
1 1 0 1 1 1 1 1
10 2
1 1 0 0 1 1 0 0 0 1
14 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1
Output
0
3
7
11
12
Note

Test Case $$$1$$$:

You don't need to do any operation.

Test Case $$$2$$$:

  1. You choose $$$i=2$$$. After your operation,$$$a=[0,1,1,0,1,1]$$$;
  2. You choose $$$i=3$$$. After your operation,$$$a=[0,0,1,1,1,1]$$$;
  3. You choose $$$i=4$$$. After your operation,$$$a=[0,0,0,1,0,1]$$$.

E2. Magic Xor(Hard Version)
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is a hard version of this problem.The only difference is $$$2 \leq k \leq 50$$$ in this version.

You are given a binary array $$$a$$$ of size $$$n$$$ consisting of $$$0$$$ or $$$1$$$.

You can do the following operation any number of times:

  • choose an index $$$i$$$ ($$$1 \lt i \lt n$$$);
  • change $$$a_{i-1}$$$ to $$$a_{i-1}\oplus a_i$$$ and change $$$a_{i+1}$$$ to $$$a_{i+1}\oplus a_i$$$. (Here $$$\oplus$$$ donates the bitwise XOR).

Your goal is to make $$$a$$$ satisfy the following condition:

  • there are at most $$$k$$$ index $$$i(1\leq i \leq n)$$$ satisfying $$$a_i=1$$$.

Find the minimum number of operations you need. It can be proven that your goal is always able to be realized.

Input

The first line of the input contains a single integer $$$t$$$($$$1\le t\le 10^5$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $$$n,k$$$($$$4\le n\le 5\cdot 10^5$$$,$$$2\leq k \leq 50$$$).

Then one line follows, containing $$$n$$$ integers $$$a_1,a_2,\cdots,a_n$$$($$$0\le a_i\le 1$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

Output

For each test case, output a single line — the minimum number of operations.

Example
Input
5
4 50
1 1 1 1
7 4
1 1 0 1 1 1 1
8 3
1 1 0 1 1 1 1 1
10 2
1 1 1 1 1 1 0 0 0 1
14 5
1 1 1 1 1 1 1 1 1 1 1 1 1 1
Output
0
1
3
15
6
Note

Test Case $$$1$$$:

You don't need to do any operation.

Test Case $$$2$$$:

You only need to choose $$$i=5$$$. After your operation,$$$a=[1,1,0,0,1,0,1]$$$.

Test Case $$$3$$$:

  1. You choose $$$i=5$$$. After your operation,$$$a=[1,1,0,0,1,0,1,1]$$$;
  2. You choose $$$i=7$$$. After your operation,$$$a=[1,1,0,0,1,1,1,0]$$$;
  3. You choose $$$i=6$$$. After your operation,$$$a=[1,1,0,0,0,1,0,0]$$$.

F. Random Noise
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You're given an array $$$a$$$ of size $$$n$$$ and $$$q$$$ queries.

Each query is one of the following three types:

  1. Set $$$a_i$$$ to value $$$x$$$.

  2. For every $$$l\leq i\leq r$$$, set $$$a_i = a_i\oplus\ 2^{v_i}$$$ where $$$v_i$$$ is a random number between $$$0$$$ and $$$19$$$ (inclusive) chosen on this operation.

  3. Output the expected value of $$$a_i\oplus a_j$$$ for randomly chosen $$$l\leq i\lt j\leq r$$$.

$$$\Large{\oplus}$$$ here denotes the xor operation.

For each type $$$3$$$ query, you should output the answer modulo $$$10^9+7$$$.

Formally, let $$$P=10^9+7$$$. It can be shown that the answer to each query of type $$$3$$$ can be expressed as an irreducible fraction $$$ab$$$, where $$$a$$$ and $$$b$$$ are integers and $$$b\not\equiv0\mod P$$$. For each query, output the integer equal to $$$a\cdot b^{-1}\mod P$$$. In other words, output an integer $$$z$$$ such that $$$0\leq z\lt P$$$ and $$$z\cdot b\equiv a\mod P$$$.

Input

First line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1\leq n,q\leq 4\cdot 10^4$$$)

Second line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ ($$$0\leq a_i\lt 2^{20}$$$)

Next $$$q$$$ lines contain queries.

First integer $$$t$$$ ($$$1\leq t\leq 3$$$) in every query denotes its type.

  • If $$$t = 1$$$, then query record contains two integers $$$i$$$ and $$$x$$$ ($$$1\leq i\leq n,0\leq x\lt 2^{20}$$$);
  • Otherwise it contains two integers $$$l$$$ and $$$r$$$ ($$$1\leq l\leq r\leq n$$$).
Output

For each type $$$3$$$ query, you should output the answer modulo $$$10^9+7$$$ in a new line.

Example
Input
3 9
15 0 7
3 1 3
1 1 0
3 1 3
2 1 1
3 1 3
1 1 0
1 3 0
2 1 3
3 1 3
Output
10
666666676
533368294
625099619