TheForces Round #35 (LOL-Forces)
A. Simple Update - I
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a binary string$$$^\dagger$$$ $$$s$$$ of length $$$n$$$ and an integer $$$k$$$.

You are allowed to do the following operation on $$$s$$$ :

  1. Choose any $$$i(k \le i \le n-k)$$$;
  2. Update all $$$s_{i},s_{i-1},s_{i-2},...,s_{i-k+2},s_{i-k+1}$$$ to $$$1$$$;
  3. Update all $$$s_{i+1},s_{i+2},s_{i+3},...,s_{i+k-1},s_{i+k}$$$ to $$$0$$$.

What are the maximum number of $$$1$$$'s in $$$s$$$ after performing the above operation infinitely many times (possibly zero)?

$$$^\dagger$$$ A binary string is a string which only contains $$$0$$$'s and $$$1$$$'s.

Input

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

The first line of each testcase contains two integers $$$n,k$$$ ($$$2 \le n \le 10^3$$$, $$$1 \le k \le ⌊\frac{n}{2}⌋$$$), the length of binary string and an integer.

The second line of each testcase contains a binary string $$$s$$$ of length $$$n$$$.

Output

For each test case, print a single integer — the maximum number of $$$1$$$'s in $$$s$$$ after performing the above operation infinitely many times(possibly zero).

Example
Input
6
2 1
00
2 1
01
3 1
101
3 1
111
4 2
1100
4 1
1010
Output
1
1
2
3
2
3
Note

In the $$$6$$$-th test case, $$$s = 1010$$$ and $$$k = 1$$$

Let choose $$$i = 2$$$, now $$$s_2$$$ becomes $$$1$$$ and $$$s_3$$$ becomes $$$0$$$. So $$$s = 1100$$$.

Let choose $$$i = 3$$$, now $$$s_3$$$ becomes $$$1$$$ and $$$s_4$$$ becomes $$$0$$$. So $$$s = 1110$$$.

Hence, maximum number of $$$1$$$'s in $$$s = 1110$$$ is $$$3$$$.

B. Simple Update - II
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a binary string$$$^\dagger$$$ $$$s$$$ of length $$$n$$$ and an integer $$$k$$$.

You are allowed to do the following operation on $$$s$$$ :

  1. Choose any $$$i(k \le i \le n-k)$$$;
  2. Update all $$$s_{i},s_{i-1},s_{i-2},...,s_{i-k+2},s_{i-k+1}$$$ to $$$1$$$;
  3. Update all $$$s_{i+1},s_{i+2},s_{i+3},...,s_{i+k-1},s_{i+k}$$$ to $$$0$$$.

For every $$$k(1 \le k \le ⌊\frac{n}{2}⌋)$$$, find the minimum number of above operations required to do on $$$s$$$ to get maximum number of $$$1$$$'s in $$$s$$$.

$$$^\dagger$$$ A binary string is a string which only contains $$$0$$$'s and $$$1$$$'s.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). 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 length of the binary string.

The second line of each testcase contains a binary string $$$s$$$ of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output

For each test case, print $$$⌊\frac{n}{2}⌋$$$ integers — minimum number of above operations required to do on $$$s$$$ to get maximum number of $$$1$$$'s in $$$s$$$.

Example
Input
5
2
10
3
100
4
0110
5
10100
7
1010010
Output
0 
1 
3 0 
3 1 
5 2 1

C1. Yet Another Nim Game (Constructive version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob decided to play the following game on $$$n$$$ piles of stones where the $$$i$$$-th$$$(1 \le i \le n)$$$ pile contains $$$p_i$$$ stones with Alice starting first :

  • On his/her turn, he/she will choose any $$$k(1 \le k \le n)$$$ distinct arbitrary piles which have a positive number of stones(note that $$$k$$$ can be chosen arbitrarily by the current player). Now the player will remove exactly one stone each from all selected $$$k$$$ piles.

The player who cannot make a move loses. Note that both Alice and Bob are intelligent, so they always play optimally.

Now your task is to construct any permutation$$$^\dagger$$$ $$$p$$$ of length $$$n$$$ such that the number of pairs ($$$l, r$$$)($$$1 \le l \le r \le n$$$), where Alice will win if both players play the game on piles $$$l, l+1, ..., r-1, r$$$, is maximum possible.

$$$^\dagger$$$ A permutation is an array of length $$$n$$$, where each number from $$$1$$$ to $$$n$$$ appears exactly once.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of piles.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output

For each test case, print $$$n$$$ integers — the required permutation $$$p$$$.

If there are multiple answers, output any.

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

C2. Yet Another Nim Game (Counting version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob decided to play the following game on $$$n$$$ piles of stones where the $$$i^{th}(1 \le i \le n)$$$ pile contains $$$p_i$$$ stones, with Alice starting first :

  • On his/her turn, he/she will choose any $$$k(1 \le k \le n)$$$ distinct arbitrary piles which have a positive number of stones(note that $$$k$$$ can be chosen arbitrarily by the current player). Now the player will remove exactly one stone each from all selected $$$k$$$ piles.

The player who cannot make a move loses. Note that both Alice and Bob are intelligent, so they always play optimally.

Now your task is to count the number of permutations$$$^\dagger$$$ $$$p$$$ of length $$$n$$$ such that the number of pairs ($$$l, r$$$)($$$1 \le l \le r \le n$$$), where Alice will win if both players play the game on piles $$$l, l+1, ..., r-1, r$$$, is maximum possible.

$$$^\dagger$$$ A permutation is an array of length $$$n$$$, where each number from $$$1$$$ to $$$n$$$ appears exactly once.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of piles.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output

For each test case, print a single integer — the required answer modulo $$$10^9 + 7$$$.

Example
Input
3
1
4
7
Output
1
12
1440

D. String From Another World
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Scientists from the NewEra got a string $$$s$$$ of length $$$n$$$ which contains lowercase English letters from far away space.

They have a machine which is capable of doing exactly one of the following operations in one second with an empty string $$$t$$$:

  1. Choose any lowercase English character and append it to the end of $$$t$$$.
  2. If $$$t$$$ is empty, do nothing; otherwise, remove the last character from $$$t$$$.

Scientists got information that within $$$m$$$ seconds the machine will die, so they decided to generate a copy of $$$s$$$ in $$$m$$$ seconds, i.e., they want to make $$$t = s$$$ by using the machine for exactly $$$m$$$ seconds.

Now the scientists are wondering in how many different ways they can make $$$t = s$$$ modulo $$$10^9 + 7$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$tc$$$ ($$$1 \le tc \le 1000$$$). The description of the test cases follows.

The first line of each testcase contains two integers $$$n,m$$$ ($$$1 \le n,m \le 8000$$$), the length of the string and the deadline of the machine.

The second line of each testcase contains a string $$$s$$$ of length $$$n$$$ which contains lowercase English letters.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases doesn't exceed $$$8000$$$.

Output

For each test case, print a single integer — the number of different ways to make $$$t = s$$$ modulo $$$10^9+7$$$.

Example
Input
5
3 4
abc
1 3
d
5 3
asdfg
7 10
wuhudsm
9 11
yugandhar
Output
1
53
0
235
261

E. Innocent Students
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a class, a test has happened and $$$n$$$ students participated in it. In this test, there is only one question and the answer to the question is an integer $$$x$$$. All the students gave their answers as integers, i.e., $$$a_i$$$ is the answer of the $$$i$$$-th$$$(1 \le i \le n)$$$ student. Student $$$i$$$ will pass the exam if |$$$x-a_i$$$| is the minimum possible among all the students who attended the exam.

Now your task is to answer $$$q$$$ queries of two types :

  1. 1 l r x : How many students will pass the exam if students $$$l, l+1, ... , r-1, r$$$ attended the exam and the answer to the question is $$$x$$$;
  2. 2 i val : Student at the $$$i$$$-th position changes his answer to $$$val$$$.
Input

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

The first line of each test case contains two integers $$$n,q$$$ ($$$1 \le n,q \le 2 \cdot 10^5$$$) — the number of students and the number of queries.

The second line of each test case contains $$$n$$$ space separated integers $$$a_{i}$$$ ($$$-10^9 \le a_{i} \le 10^9$$$) — the answer from the $$$i$$$-th student.

The next $$$q$$$ lines contain one of the two forms:

  1. 1 l r x $$$(1 \le l \le r \le n)$$$ and $$$(-10^9 \le x \le 10^9)$$$;
  2. 2 i val $$$(1 \le i \le n)$$$ and $$$(-10^9 \le val \le 10^9)$$$.

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

It is guaranteed that the sum of $$$q$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case — print the required answer for the $$$1$$$-st type query.

Example
Input
2
3 5
1 -2 3
1 1 3 0
2 3 -2
1 2 3 1
2 1 -4
1 1 1 -10
7 8
1 2 4 2 4 6 7
1 3 5 5
1 1 7 5
2 1 6
2 4 4
1 1 7 5
1 1 3 2
2 7 1
1 1 7 -1
Output
1
2
1
2
3
5
1
1

F. Red Blue Tree
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree containing $$$n$$$ nodes where each node is either red node or blue node and the value of the node $$$i$$$ is $$$a_i(1 \le i \le n)$$$.

Let $$$R$$$ be the number of red nodes and $$$B$$$ be the number of blue nodes, then beauty of the tree is defined as ($$$\sum_{i = 1}^R a_i - \sum_{i = 1}^B a_i$$$), i.e., difference between sum of values of all red nodes and sum of values of all blue nodes.

A tree will be called "Perfect Tree" if it satisfies the following conditions :

  • $$$R \gt 0$$$ and $$$B \gt 0$$$.
  • Beauty of the tree $$$\ge 0$$$.

A Forest will be called "Perfect Forest" if atleast one of it's tree is a Perfect tree. Otherwise it will be a "Non-Perfect Forest".

Find the minimum number of edges to remove from the given tree to make the forest "Non-Perfect Forest".

Input

The first line of each test contains single integer $$$n$$$ $$$(1 \le n \le 8000)$$$ — the size of the tree.

The next line contains $$$n$$$ space-seperated integers $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$ — the value of the $$$i^{th}$$$ node.

The next line contains a binary string $$$S$$$ of length $$$n$$$, where $$$S_i = 0$$$ indicates that $$$i^{th}$$$ node is red node, $$$S_i = 1$$$ indicates that $$$i^{th}$$$ node is blue node.

The next $$$n-1$$$ lines contain two integers $$$x,y$$$ $$$(1 \le x,y \le n, x≠y)$$$ — there is an edge between $$$x$$$ and $$$y$$$.

Output

For each test, print single integer — the minimum number of edges to remove from the given tree to make the forest "Non-Perfect Forest"

Examples
Input
6
2 4 3 6 5 1
011001
5 4
3 1
6 5
1 5
2 3
Output
1
Input
7
9 10 11 5 2 3 6
0010110
3 1
6 4
1 2
3 5
4 7
4 1
Output
2
Note

In the first test, The beauty of the tree is $$$(2+6+5) - (4+3+1) = 5$$$, i.e., beauty $$$\ge 0$$$ and $$$(R = 3 \gt 0)$$$ and $$$(B = 3 \gt 0)$$$. So the given tree is "Perfect tree" and the forest is "Perfect Forest".

After removing the edge between nodes $$$4$$$ and $$$5$$$.

The Beauty of the tree containing nodes {$$$1,2,3,5,6$$$} is $$$(2+5) - (3+4+1) = -1$$$ i.e., beauty $$$ \lt 0$$$. So this tree is "Non-Perfect Tree".

The Beauty of the tree containing nodes {$$$4$$$} is $$$(6) - () = 6$$$ i.e., beauty $$$\ge 0$$$ but $$$(B = 0)$$$. So this tree is "Non-Perfect Tree".

As both trees are "Non-Perfect Tree". The resultant forest is "Non-Perfect Forest". Hence minimum number of edges to remove from the given tree to make the forest "Non-Perfect Forest" is $$$1$$$.