TheForces Round #24 (DIV3-Forces)
A. Banis and Cards
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ cards numbered from $$$1$$$ to $$$n$$$ on the table, and Banis will choose a number $$$m$$$ and try to find the sum of all cards such that the number of the card$$$ \% m = 0$$$, but he's too lazy that he doesn't want to solve it by himself, and that's why he gives the task to you.

Can you help him solve this problem?

Input

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

The only line of each test case contains two numbers $$$n,m(1 \le m\le n\le 10^9)$$$

Output

For each test case, print the answer.

Example
Input
3
12 2
1 1
1010 10
Output
42
1
51510

B. Left or Right Shift
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given a string $$$s$$$ of $$$n$$$ lowercase characters and an integer $$$k$$$.

In one operation, you can shift a character left, or shift a character right.

Shift a character left means shift $$$a$$$ to $$$z$$$,$$$b$$$ to $$$a$$$,...,or $$$z$$$ to $$$y$$$.

Shift a character right means shift $$$a$$$ to $$$b$$$,$$$b$$$ to $$$c$$$,...,or $$$z$$$ to $$$a$$$.

What is the lexographically smallest string you can obtain after exactly $$$k$$$ moves?

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 two integers $$$n,k$$$ ($$$1\le n \le 4 \cdot 10^5,1\le k \le 10^9$$$).

The second line contains a string $$$s$$$ of length $$$n$$$ composed of lowercase letters.

The sum of $$$n$$$ over all test cases will not exceed $$$4 \cdot 10^5$$$.

Output

For each test case, output on a new line — the lexographically smallest string you can obtain.

Example
Input
3
1 3
a
3 10
zkb
4 12
ycew
Output
b
abb
aaaa

C. Yet Another ÷2 or +1 Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For a string $$$t$$$ of length $$$m$$$,note:

$$$$$$f(t)=\begin{cases}t_1...t_mt_m,\quad\text{t is a palindrome}\\t_1...t_{\lfloor \frac{m}{2} \rfloor},\quad\text{Otherwise} \end{cases}$$$$$$

A palindrome is a string that reads the same forward and backward.

For a given string $$$s$$$ of length $$$n$$$ and a given number $$$k$$$,find $$$f(...f(f(s)))$$$($$$k$$$ times).

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 two integers $$$n,k$$$ ($$$1\le n,k \le 10^{6}$$$).

The second line contains a string $$$s$$$ of length $$$n$$$ composed of lowercase letters.

The sum of $$$n,k$$$ over all test cases will not exceed $$$10^6$$$.

Output

For each test case, output on a new line — $$$f(...f(f(s)))$$$($$$k$$$ times).

Example
Input
3
2 2
ab
6 3
abaaba
8 3
cabsuixq
Output
aa
abaa
c
Note

Test Case $$$1$$$:

$$$f(f(ab))=f(a)=aa$$$.

Test Case $$$2$$$:

$$$f(f(f(abaaba)))=f(f(abaabaa))=f(aba)=abaa$$$.

D. Sum and Difference
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given three numbers $$$n,l,$$$ and $$$r$$$.

Your task is to construct an array $$$a$$$ with $$$n$$$ integers which satisfies the following conditions:

  1. $$$l\le a_i\le r$$$;
  2. For all $$$i(1 \leq i \leq n-1)$$$,$$$|a_i-a_{i+1}|$$$ is prime;
  3. For all $$$i(1 \leq i \leq n-1)$$$,$$$(a_i+a_{i+1})$$$ is distinct.

If this is impossible, return $$$-1$$$.

NOTE: 0 and 1 are both not prime numbers.

Input

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

The only line of each test case contains three numbers $$$n,l,r(2 \le n\le 1000,1 \le l\le r\le 2000)$$$.

Output

For each test case, output $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$.

If there are multiple solutions, print any of them.

If there is no solution, print a single integer $$$−1$$$.

Example
Input
3
3 1 4
5 1 4
5 10 20
Output
1 4 2
-1
10 15 12 19 14

E. L-shaped Dominoes
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a $$$2*n$$$ grid, where each cell contains an integer (not necessarily non-negative).

Your task is to find a way to place non-overlapping L-shaped dominoes on this grid, so that the sum of integers on the cells covered by the dominoes is maximum.

An L-shaped domino can be seen as a $$$2*2$$$ domino obtained by removing a $$$1*1$$$ domino.

For example,for the following $$$2*5$$$ grid, the optimal way is shown in the right picture.

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 contains $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$),representing the $$$n$$$ numbers in the first row of this grid.

The third line of contains $$$n$$$ integers $$$b_1,b_2,\ldots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$),representing the $$$n$$$ numbers in the second row of this grid.

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

Output

For each test case, print a single integer in a new line — the maximum sum you can get.

Example
Input
3
3
-1 -1 -1
-1 -1 -1
5
10 9 10 10 9
10 10 -20 10 9
6
123 -183 100 -213 901 910
281 -182 281 211 129 -999
Output
0
60
2754
Note

Test Case $$$1$$$:

You don't need to place any dominoes.

Test Case $$$2$$$:

The optimal way is shown in the picture above.

F1. Maximum Flow in DIV3?(Easy Version)
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The only difference between the two versions are the constraints on $$$l$$$ and $$$r$$$.

There is a flow network with $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$.The source node is vertex $$$1$$$, and the sink node is vertex $$$n$$$.

The following condition holds:

  • For every distinct positive integers $$$a$$$, $$$b(1\leq a,b \leq n)$$$,if $$$a$$$ is divided by $$$b$$$, then there is an edge from node $$$b$$$ to node $$$a$$$, with capacity $$$\frac{a}{b}$$$.

Calculate the sum of the maximum flow of the flow network, in all $$$n \in [l,r]$$$, mod $$$998244353$$$.

i.e) Let's call the maximum flow of $$$n = i$$$ by $$$flow(i)$$$, Then you should calculate the $$$ \left( \sum_{i=l}^r flow(i) \right)\mod 998244353 $$$.

Input

The first line of the input contains an integer $$$t (1 \le t \le 100)$$$ — the number of test cases.

Then follow the descriptions of the test cases.

Each test case consists of one line, contains two integers $$$l$$$ and $$$r$$$ $$$(2 \le l = r \le 10^{14})$$$ — described in statement.

The sum of $$$r$$$ over all test cases does not exceed $$$10^{14}$$$.

Output

Print out $$$t$$$ lines, each of which is the answer to the corresponding test case — the maximum flow of given flow network.

Example
Input
3
2 2
3 3
6 6
Output
2
3
10
Note

In the first case, the flow network is as follows:

Capacity of edge is written on the edge.

In the second case, the flow network is as follows:

In the third case, the flow network is as follows:

F2. Maximum Flow in DIV3?(Hard Version)
time limit per test
6 s
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The only difference between the two versions are the constraints on $$$l$$$ and $$$r$$$.

There is a flow network with $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$.The source node is vertex $$$1$$$, and the sink node is vertex $$$n$$$.

The following condition holds:

  • For every distinct positive integers $$$a$$$, $$$b(1\leq a,b \leq n)$$$,if $$$a$$$ is divided by $$$b$$$, then there is an edge from node $$$b$$$ to node $$$a$$$, with capacity $$$\frac{a}{b}$$$.

Calculate the sum of the maximum flow of the flow network, in all $$$n \in [l,r]$$$, mod $$$998244353$$$.

i.e) Let's call the maximum flow of $$$n = i$$$ by $$$flow(i)$$$, Then you should calculate the $$$ \left( \sum_{i=l}^r flow(i) \right)\mod 998244353 $$$.

Input

The first line of the input contains an integer $$$t (1 \le t \le 100)$$$ — the number of test cases.

Then follow the descriptions of the test cases.

Each test case consists of one line, contains two integers $$$l$$$ and $$$r$$$ $$$(2 \le l \le r \le 10^{14})$$$ — described in statement.

The sum of $$$r$$$ over all test cases does not exceed $$$10^{14}$$$.

Output

Print out $$$t$$$ lines, each of which is the answer to the corresponding test case.

Example
Input
3
2 3
6 9
10 15
Output
5
41
99

G. Useless Trick
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a binary string $$$s$$$. A binary string is called good if every substring of size $$$m$$$ has exactly $$$k$$$ number of $$$1$$$.

You can do this as many times operation as you like, in one operation you can choose an interval $$$[l,r]$$$ and flip it (turn $$$0$$$ into $$$1$$$, turn $$$1$$$ into $$$0$$$). You want to find the minimum number of operations to make the string good.

Input

Each test contains multiple test cases.

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

The first line of each test case contains three integer $$$n,m,k$$$ ($$$1\le k\le m\le n\le3000$$$).

The second line of each test case contains a single binary string $$$s$$$.

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

Output

For each test case, print a single integer — the minimum number of operations.

Example
Input
3
7 5 4
0011101
7 7 6
0100010
16 4 2
1111101010000000
Output
1
2
4
Note

In the first case, we can choose interval $$$[2,2]$$$, then $$$s=0111101$$$, it's good.

In the second case, we can choose interval $$$[3,7]$$$ and $$$[6,6]$$$, then $$$s=0111111$$$, it's good.