TheForces Round #21 (EDU-Forces)
A. Interesting Index
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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

You can do the following two types of operations any number of times:

  • Rerange the array in any order;
  • Make $$$a_i:=-a_i(1\leq i \leq n)$$$.
An index $$$i(2\leq i \leq n)$$$ is called interesting if and only if $$$(a_1+...+a_{i-1}) \dot (a_1+...+a_i) \leq 0$$$.

Output any array $$$a$$$ after your operations,which maximizes the number of interesting indexes.

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 2\cdot 10^5$$$).

The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$0 \le a_i \lt 10^9$$$).

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 on a new line — an array $$$a$$$ after your operations,which maximizes the number of interesting indexes.

Example
Input
2
3
2 0 2
4
3 4 5 6
Output
2 -2 0
-4 5 -3 6
Note

Test Case $$$1$$$:

$$$a_1(a_1+a_2)=2*0=0,i=2$$$ is interesting;

$$$(a_1+a_2)(a_1+a_2+a_3)=0*0=0,i=3$$$ is interesting.

The number of interesting indexes is $$$2$$$.It shows that $$$2$$$ is the maximum.

Test Case $$$2$$$:

$$$a_1(a_1+a_2)=-4*1=-4,i=2$$$ is interesting;

$$$(a_1+a_2)(a_1+a_2+a_3)=1*(-2)=-2,i=3$$$ is interesting;

$$$(a_1+a_2+a_3)(a_1+a_2+a_3+a_4)=-2*4=-8,i=4$$$ is interesting.

The number of interesting indexes is $$$3$$$.It shows that $$$3$$$ is the maximum.

B. Magical Deletion
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a magic string $$$s$$$ that consists of lowercase Latin letters and an integer $$$k$$$ $$$(k \lt |s|)$$$.

You can do the following operation exactly once:

  1. Choose a positive integer $$$a$$$ where $$$1 \leq a \leq |s|-k+1$$$.
  2. Let $$$s = \overline{c_1 c_2 \dots c_{|s|-1} c_{|s|}}$$$ where $$$c_i$$$ indicates the $$$i$$$-th character in $$$s$$$. Delete the substring $$$\overline{c_a c_{a+1} \dots c_{a+k-2} c_{a+k-1}}$$$ and then concatenate the remaining characters into a new string $$$x = \overline{c_1 c_2 \dots c_{a-2} c_{a-1} c_{a+k} c_{a+k+1} \dots c_{|s|-1} c_{|s|}}$$$ where the length of the string $$$x$$$ is $$$|s|-k$$$.

A magic string $$$y$$$ is said to be weaker that a magic string $$$z$$$ of the same length if at the leftmost position where the character inside $$$y$$$ and $$$z$$$ is different, the character inside $$$y$$$ appears earlier in the alphabet than the character inside $$$z$$$.

More formally, let $$$l$$$ be the leftmost position where the character inside $$$y$$$ and $$$z$$$ differs. Then, $$$y_l \lt z_l$$$. For example, the magic string $$$y =$$$ "codeforall" is weaker than the magic string $$$z =$$$ "codeforces" since the leftmost position where they differ is the $$$8$$$-th position and $$$y_8 =$$$ 'a' $$$ \lt $$$ 'c' $$$= z_8$$$.

Find the weakest possible string that you can achieve.

Input

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

The only line for each test case contains a string $$$s$$$ consisting of lowercase Latin letters followed by an integer $$$k$$$ $$$(1 \leq k \lt |s| \leq 4 \cdot 10^5)$$$.

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

Output

For each test case, output a string $$$x$$$ — the weakest magic string obtained after the operation.

Example
Input
5
haiti 2
ptlwqak 4
amogus 2
inthatpi 5
icodeforces 1
Output
hai
pak
agus
ini
codeforces
Note

For the first test case, we can delete the segment $$$[4,5]$$$ to get the string "hai". Other strings we can obtain by deleting other segments are "hti" and "iti". From all the possible strings obtained, the weakest one is "hai".

For the fifth test case, it can be proven that we can get the weakest magic string by deleting the segment $$$[1,1]$$$.

C. Legendary Drop
time limit per test
4 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Teadose(IanISam) has been getting "Legendary Drops" $$$ $$$ in his recent codeforces contests. After learning about persistent data structures, Teadose can now time travel and warn his past self to not take at most one contest(Teadose refuses to skip more than one round) to minimize the Legendary Drop*.

Teadose will participate in $$$n$$$ contests, the $$$i^{th}$$$ of which Teadose has a performance of $$$p_i$$$ and is a division $$$d_i$$$ contest, where $$$d_i$$$ denotes the division of the contest modulo 2. Teadose will take only Division $$$1$$$ and $$$2$$$ rounds and his rating, $$$r$$$ after a contest $$$i$$$ will be: $$$$$$ \begin{cases} r & d_i = 0 , r \ge 2100\\ r & d_i = 1, r \lt 1900 \\ r + f(\frac{(p-r)}{4}) & \text{else} \end{cases} $$$$$$ Here $$$f(x)$$$ rounds x to an integer closer to zero. For example $$$f(1.5)=1$$$, $$$f(-1.5)=-1$$$, $$$f(-1)=-1$$$. Find the minimum Legendary drop Teadose will get if he warns himself on at most one contest. Note: Teadose does not have to warn his past self if taking all contests will already minimize his Legendary Drop.

*The minimum Legendary Drop is minimizing Teadose's initial rating - Teadose's final rating

Input

The first line contains two integers $$$n$$$ $$$(1\leq n\leq 10^5)$$$ and $$$k$$$ $$$(0\leq k\leq 4000)$$$ the number of contests and Teadose's initial rating

The second line contains $$$n$$$ integers, $$$p_1, p_2, p_3 ... p_n$$$ $$$(0\leq p_i\leq 4000)$$$ Teadose's performance on the $$$i^{th}$$$ contest

The third line contains $$$n$$$ integer $$$d_1, d_2, d_3 ... d_n$$$ $$$ (d_i ={0, 1})$$$ the division of the $$$i^{th}$$$ contest where $$$0$$$ indicates that the $$$i^{th}$$$ contest is division $$$2$$$ and $$$1$$$ indicating a division $$$1$$$ contest

Output

Print one integer, Teadose's minimum Legendary Drop if he can avoid at most one contest

Examples
Input
5 1800
2444 1689 1861 1577 1736
0 1 0 0 0
Output
-48
Input
2 2100
1296 0
1 1
Output
201
Note

On the first test, it is optimal to skip the $$$4^{th}$$$ contest $$$1800 \xrightarrow[\text{rated}]{(div2, p2444)} 1961 \xrightarrow[\text{rated}]{(div1, p1689)} 1893 \xrightarrow[\text{rated}]{(div2, p1861)} 1885 \xrightarrow[\text{skipped}]{(div2, p1588)} 1885 \xrightarrow[\text{rated}]{(div2, p1736)} 1848$$$

Thus the minimum legendary drop possible is $$$1800 - 1848 = -48$$$

On the second test, one optimal solution is taking every contest.

$$$2100 \xrightarrow[\text{rated}]{(div1, p1296)} 1899 \xrightarrow[\text{unrated}]{(div1, p0)} 1899$$$

Thus the minimum legendary drop possible is $$$2100 - 1899 = 201$$$

D. RPS Club Activity
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ people in a room, and they are playing the $$$n$$$-person version of RPS (Rock, Paper, Scissors). There are three types of moves — rock, paper, and scissors. Rock beats scissors, paper beats rock, and scissors beat paper.

A round of the game works as follows:

  1. All people who are currently in the room simultaneously make a move. Every person has $$$a\%$$$ probability of making rock, $$$b\%$$$ probability of making paper, and $$$c\%$$$ probability of making scissors;
  2. If there are one or three distinct types of moves made by these people, the round ends, and no one exits the room;
  3. If there are two distinct types of moves, all people who made the losing move leave the room and never come back again. People who made the winning move stay in the room. Then the round ends.

The game ends when there is only one person in the room.

What is the expected number of rounds to be played in the game? Print this number modulo $$$10^9+7$$$. If the expected number can be arbitrarily large, print $$$-1$$$.

Input

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

The only line of each test case contains four integers $$$n, a, b, c$$$ $$$($$$$$$1 \leq n \leq 2000$$$, $$$0 \leq a, b, c \leq 100$$$, $$$a+b+c=100$$$$$$)$$$ — the number of people in the room to begin with and the probabilities of making rock, paper, and scissors.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output

For each test case, output one line containing one integer — the expected number of rounds in the game.

Example
Input
5
2 0 50 50
2 25 25 50
3 25 25 50
1 30 30 40
10 100 0 0
Output
2
200000003
123809527
0
-1
Note

In the first test case, the probability for having $$$1$$$ round is $$$\frac{1}{2}$$$, the probability for having $$$2$$$ rounds is $$$\frac{1}{4}$$$, the probability for having $$$3$$$ rounds is $$$\frac{1}{8}$$$, and so on. Thus, the answer is $$$\sum_{i = 1}^{\infty}\frac{i}{2^i} = 2$$$.

In the second test case, it can be shown that the expected number can be written as $$$\frac{8}{5}$$$. It can be shown that $$$\frac{8}{5} \equiv 200000003 \pmod {10^9+7}$$$, so $$$200000003$$$ is printed.

In the third test case, it can be shown that the expected number can be written as $$$\frac{244}{105}$$$.

E. Binary Function
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

While AHF loves short descriptions, he has noticed that the descriptions for earlier problems have been longer than he wanted. Therefore, he decided to keep this problem's description as short as possible.

Let us declare function $$$f(x)$$$ for a positive number $$$x$$$ as the number of adjacent indices $$$i$$$ $$$(0 \le i \lt \lfloor{\log _2 x }\rfloor)$$$ in $$$B$$$, defined as the binary representation of $$$x$$$, meeting the condition $$$B_i \neq B_{i+1}$$$, for example, $$$f(5) = f({101}_2) = 2$$$.

You're given positive integers $$$k$$$ and $$$n$$$, calculate how many numbers $$$x$$$ exist, such that $$$1 \le x \le n$$$ and $$$f(x) = k$$$, As AHF considers this easy for only one query, He wants you to answer $$$q$$$ independent queries.

Input

On the first line of the input, you will receive a positive integer $$$q$$$ ($$$1 \le q \le 10^5$$$), which is the number of queries. On the $$$q$$$ following lines, you will receive two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le 60$$$, $$$1 \le n \le 2^{60} - 1$$$) in corresponding order.

Output

For each query, output the answer in one line.

Example
Input
10
6 2
1 60
94 3
32 5
98 3
123 2
2012 5
3443 24
54543 12
3232123 10
Output
1
0
25
0
26
34
461
0
499
536402

F. Hacked!
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice is planning on participating in TheForces round next week, a highly anticipated competitive programming contest where she aims to maximize her score by solving problems. However Bob, her rival, wants to minimize Alice's score by hacking her submissions during the contest.

The contest is scheduled to last for $$$T$$$ minutes and will consist of $$$n$$$ problems. The $$$i$$$-th problem will take Alice $$$t_i$$$ minutes to solve and yields $$$a_i$$$ points upon solving.

At the beginning of the contest, Alice will choose some problems that can be solved within the duration. However, Bob plans on hacking one of her solutions. He will be prepared to do so immediately after she has solved all her chosen problems and will do so in a way that minimizes Alice's final score.

If Alice is hacked on the $$$i$$$-th problem, she will lose the $$$a_i$$$ points she received for it. Fixing it will take an additional $$$f_i$$$ minutes. If she is able to fix it before the contest ends, she will recover the points but with a penalty $$$p_i$$$, i.e. she will only gain $$$(a_i - p_i)$$$ points. In case she is not able to fix it in time, she will not gain any points for the problem.

For example, consider the case when $$$n = 2$$$ and $$$T = 25$$$ and

  • $$$t_1 = 10$$$, $$$a_1 = 50$$$, $$$f_1 = 3$$$ and $$$p_1 = 25$$$
  • $$$t_2 = 10$$$, $$$a_2 = 60$$$, $$$f_2 = 5$$$ and $$$p_2 = 20$$$
Alice solves the first problem at $$$t = 10$$$ and the second problem at $$$t = 20$$$. Bob hacks the first problem. Alice fixes it by $$$t = 23$$$. In doing so Alice scores $$$(50 - 25) + 60 = 85$$$ points. If $$$T = 20$$$, Bob could hack the second problem and Alice would score $$$50 + 0 = 50$$$ points.

Note that Bob will make only one hack during the contest.

Alice knows that Bob will do this. Assuming they make their choices optimally, what is the maximum score Alice can get?

Input

The first line of each test case contains an integer $$$tc$$$ $$$(1 \leq tc \leq 200)$$$ — the number of test cases. The description of each test case is as follows.

The first line of each test case contains two integers $$$n$$$ and $$$T$$$ $$$(1 \le n, T \le 500)$$$ — the number of problems and the duration of the contest.

The next $$$n$$$ lines describe each problem. The $$$i$$$-th line contains four integers $$$t_i$$$, $$$a_i$$$, $$$f_i$$$ and $$$p_i$$$ $$$(1 \le t_i, f_i \le T, 1 \le p_i \le a_i \le 10^6)$$$ — the time needed to solve it, the points gained for solving it, the time needed to fix it if hacked, and the penalty received if it is fixed after it is hacked.

The sum of $$$n$$$ over all test cases does not exceed $$$500$$$. The sum of $$$T$$$ over all test cases does not exceed $$$500$$$.

Output

For each test case, print a single integer — the maximum score Alice can get.

Example
Input
5
1 3
3 5 1 2
1 4
3 5 1 2
2 25
10 50 3 25
10 60 5 20
2 20
10 50 3 25
10 60 5 20
2 5
5 100 1 1
4 2 1 1
Output
0
3
85
50
1
Note

In the first test case, Alice solves the problem at $$$t = 3$$$. Bob hacks Alice's submission. Alice does not have any time left to fix it. Hence Alice gains $$$0$$$ points.

In the second test case, Alice solves the problem at $$$t = 3$$$. Bob hacks Alice's submission. Alice fixes her solution by $$$t = 4$$$. Hence Alice gains $$$(5-2)=3$$$ points.

The third and fourth test cases are explained above in the statemet.

G. Revolving Sushi
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ circular positions on the table in the sushi restaurant.

Initially, there are $$$x_i$$$ pieces of sushi in the plate at position $$$i$$$.Every second,the plate at position $$$i$$$ will be put into $$$a_i$$$ pieces of sushi.Then,the plates will revolve.

Formally:

  • The plate at position $$$1$$$ will move to position $$$2$$$;
  • The plate at position $$$2$$$ will move to position $$$3$$$;
  • ...
  • The plate at position $$$n$$$ will move to position $$$1$$$.

If for each position,the number of sushi is a multiple of $$$k$$$,customers will be happy.

Find the minimum waiting time to make customers happy.If no solution,output $$$-1$$$ instead.

Input

The first line of input will contain a single integer $$$t(t \leq 10^5)$$$, denoting the number of test cases.

Each test case contains three lines.

The first line contains two space-separated integers $$$n$$$,$$$k(1\leq n \leq 4*10^5,1\leq k \leq 10^9)$$$.

The next line contains $$$n$$$ integers:$$$x_1$$$,$$$x_2$$$,...$$$x_n(1 \leq x_i \leq 10^9)$$$.

The next line contains $$$n$$$ integers:$$$a_1$$$,$$$a_2$$$,...$$$a_n(1 \leq a_i \leq 10^9)$$$.

It's guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$4*10^5$$$.

Output

For each test case,output on a new line — the minimum waiting time to make customers happy.If no solution,output $$$-1$$$ instead.

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

Test case $$$1$$$:

Note $$$p_i$$$ as the number of sushi in the plate currently in position $$$i$$$.

Initially:$$$p=[1,2,3]$$$;

The $$$1_{st}$$$ second:$$$p=[5,2,4]$$$;

The $$$2_{nd}$$$ second:$$$p=[6,6,4]$$$.

After $$$2$$$ seconds, all numbers are multiples of $$$k=2$$$, so the answer is $$$2$$$.