close

Kotlin Heroes: Episode 14
A. Game
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Alice and Bob are playing a card game. The game consists of $$$3$$$ rounds, in each round both players score some points (from $$$0$$$ to $$$k$$$), and for each round, Alice's score differs from Bob's score. The player who scores more points in a round is considered the winner of that round.

In the first round, Alice scored $$$a_1$$$ points, and Bob scored $$$b_1$$$. In the second round, Alice scored $$$a_2$$$ points, and Bob scored $$$b_2$$$.

The winner of the game is the one who has the higher total score. If Alice's total score equals Bob's total score, the player who won more rounds is declared the winner. Alice wants to understand if Bob has a chance to win, or if she will definitely win regardless of the results of the $$$3$$$-rd round. Help her determine this!

Please note that in each round, a player can score at least $$$0$$$ and at most $$$k$$$ points. Additionally, for each round, Alice's score differs from Bob's score.

Input

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

Each test case consists of three lines:

  • the first line contains a single integer $$$k$$$ ($$$1 \le k \le 50$$$) — the maximum number of points that can be scored in a round;
  • the second line contains two integers $$$a_1$$$ and $$$b_1$$$ ($$$0 \le a_1, b_1 \le k$$$; $$$a_1 \ne b_1$$$) — the points scored by Alice and Bob respectively in the first round;
  • the third line contains two integers $$$a_2$$$ and $$$b_2$$$ ($$$0 \le a_2, b_2 \le k$$$; $$$a_2 \ne b_2$$$) — the points scored by Alice and Bob respectively in the second round.
Output

For each test case, output NO if Alice will win regardless of the results of the third round, or YES if Bob has a chance to win.

Example
Input
5
6
2 3
1 4
5
3 1
3 1
3
3 1
3 1
10
0 1
10 0
4
3 1
3 1
Output
YES
YES
NO
YES
NO
Note

In the first example, Bob will win if, for example, Alice scores $$$3$$$ points in the last round, and Bob scores $$$2$$$.

In the second example, Bob will win if Alice scores $$$0$$$ points in the last round, and Bob scores $$$5$$$.

B. Two Towers
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You have two towers made of blocks, standing next to each other. Initially, the height of the first tower is $$$a$$$, and the height of the second tower is $$$b$$$.

In one action, you can:

  • take one block and place it on one of the towers, increasing its height by $$$1$$$;
  • or take two blocks and place one on each tower, increasing both heights by $$$1$$$. However, this can only be done if their heights are equal.

Your goal is to make the height of the first tower equal to $$$c$$$, and the height of the second tower equal to $$$d$$$. What is the minimum number of actions you need to perform?

Input

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

Each test case consists of one line containing $$$4$$$ integers $$$a, b, c, d$$$ ($$$1 \le a \le c \le 10^8$$$; $$$1 \le b \le d \le 10^8$$$).

Output

For each test case, output one integer — the minimum number of actions that you have to perform.

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

In the first example, you can first place a block on the first tower, making the heights of both towers equal to $$$2$$$. Then, you can place one block on each tower, raising their heights to $$$3$$$. After that, you can place two blocks on the second tower, increasing its height to $$$5$$$. Thus, in $$$4$$$ moves, you can make the height of the first tower equal to $$$3$$$ and the second tower equal to $$$5$$$.

C. Minesweeper
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You need to construct a field for the game "Minesweeper" consisting of $$$2$$$ rows and several columns. Each cell must either be empty or contain a mine. We say that two cells are neighboring if they share a side and/or a corner.

The field you are constructing must satisfy the following constraints:

  • each empty cell must be neighboring at most one mine;
  • the number of empty cells that have a neighboring cell with a mine is equal to $$$k$$$;
  • among all suitable fields, the number of columns must be the minimum possible.

Construct such a field or report that it is impossible.

Input

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

Each test case consists of one line containing one integer $$$k$$$ ($$$1 \le k \le 100$$$) — the required number of empty cells which have a neighboring cell with a mine.

Output

For each test case, output the answer as follows:

  • if it is impossible to construct a field that satisfies all constraints, print NO;
  • otherwise, on the first line print YES, and on the second line print an integer $$$n$$$, where $$$n$$$ is the minimum number of columns in the field. On the third and fourth lines, print the description of the field itself. The description of each row of the field must consist of $$$n$$$ characters, each of which is either a dot "." (empty cell) or an asterisk "*" (mine). If there are multiple suitable fields, output any of them.
Example
Input
5
1
4
8
10
9
Output
YES
1
*
.
NO
YES
5
*....
...*.
YES
6
.*..*.
......
NO

D. Two Arrays
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The median of the sequence $$$[s_1, s_2, \dots, s_k]$$$ is defined as the element that appears at position $$$\lfloor \frac{k+1}{2} \rfloor$$$ when the sequence is sorted in non-decreasing order. For example, the median of the sequence $$$[4, 5, 6, 1, 2, 2]$$$ is $$$2$$$; the median of the sequence $$$[3, 6, 3, 4, 5]$$$ is $$$4$$$.

You are given two arrays $$$[a_1, a_2, \dots, a_n]$$$ and $$$[b_1, b_2, \dots, b_m]$$$, sorted in non-decreasing order. Both arrays have odd lengths.

In one operation, you can do the following:

  • choose one of the arrays and mark an odd number of elements in it;
  • calculate $$$x$$$ — the median of the marked elements;
  • remove all marked elements;
  • insert $$$x$$$ into any position of the array on which the operation was performed.

Your task is to determine whether it is possible to make the arrays equal.

Input

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

Each test case consists of three lines:

  • the first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$);
  • the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le 10^9$$$);
  • the third line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_1 \le b_2 \le \dots \le b_m \le 10^9$$$).

Additional constraints on the input:

  • the sum of $$$(n+m)$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$;
  • in every test case, $$$n \bmod 2 = 1$$$ and $$$m \bmod 2 = 1$$$.
Output

For each test case, output YES if it is possible to make the arrays equal, or NO if it is not possible.

Example
Input
3
5 3
1 2 3 4 5
1 3 7
3 5
11 17 19
19 20 26 29 37
1 7
11
1 2 7 9 11 15 17
Output
YES
NO
YES
Note

In the first example, the arrays can be made equal by applying the following sequence of operations:

  1. for the array $$$a = [1, 2, 3, 4, 5]$$$, mark the $$$2$$$-nd, $$$4$$$-th, and $$$5$$$-th elements. Their median is $$$4$$$. We insert it at the end of the array, resulting in $$$a = [1, 3, 4]$$$;
  2. for the array $$$b = [1, 3, 7]$$$, mark all elements. Their median is $$$3$$$. We get the array $$$b = [3]$$$;
  3. for the array $$$a = [1, 3, 4]$$$, mark all elements. Their median is $$$3$$$. We get the array $$$a = [3]$$$;
  4. now the arrays $$$a$$$ and $$$b$$$ are equal.

E. Supersequence
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

An array $$$a$$$ is called a subsequence of an array $$$b$$$ if some elements can be removed from array $$$b$$$ (possibly all, possibly none) to obtain the array $$$a$$$.

You are given an array $$$a = [a_1, a_2, \dots, a_n]$$$. We call an array $$$b = [b_1, b_2, \dots, b_m]$$$ beautiful if:

  • $$$a$$$ is a subsequence of $$$b$$$;
  • for each $$$i$$$ from $$$1$$$ to $$$m-1$$$, the elements $$$b_i$$$ and $$$b_{i+1}$$$ differ by exactly $$$1$$$ (that is, $$$|b_i - b_{i+1}| = 1$$$);
  • among all arrays that satisfy these two requirements, the length of $$$b$$$ is minimum.

You have to process $$$q$$$ queries. In the $$$i$$$-th query, a single integer $$$x_i$$$ is given. Your task is as follows:

  • if $$$x_i$$$ is greater than the minimum possible number of elements in a beautiful array, print $$$-1$$$;
  • otherwise, if the same number occupies position $$$x_i$$$ in all beautiful arrays, print that number;
  • otherwise, print $$$0$$$.
Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

The third line contains $$$q$$$ integers $$$x_1, x_2, \dots, x_q$$$ ($$$1 \le x_i \le 10^{18}$$$).

Output

For each query, print a single integer — the answer to it.

Example
Input
5 16
4 1 1 5 9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Output
4 3 2 1 0 1 2 3 4 5 6 7 8 9 -1 -1

F. Self-Produced Sequences
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Let's call an integer sequence self-produced if for every $$$i$$$ ($$$1 \le i \le n$$$) at least one of the following conditions holds:

  • $$$a_i$$$ is equal to the sum of the elements on the left (i. e. $$$a_i = \displaystyle\sum\limits_{j = 1}^{i - 1} a_j$$$);
  • $$$a_i$$$ is equal to the sum of the elements on the right (i. e. $$$a_i = \displaystyle\sum\limits_{j = i + 1}^{n} a_j$$$).

Note that $$$0$$$ at the beginning/end of the sequence is also considered valid.

You are given an integer array $$$a$$$ of size $$$n$$$. Your task is to calculate the number of self-produced subsequences of the array $$$a$$$. Since the answer might be large, print it modulo $$$998244353$$$. Two subsequences are different if the indices of chosen elements are different.

Input

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

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the number of self-produced subsequences of the array $$$a$$$ taken modulo $$$998244353$$$.

Example
Input
5
3
1 1 2
2
0 0
5
0 1 0 1 0
6
1 0 2 2 1 1
11
2 0 3 1 0 0 2 3 0 3 2
Output
2
4
12
8
41

G. Jammer
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

On a field of size $$$n \times m$$$, there is a robot located at point $$$(0, 0)$$$, whose task is to reach point $$$(n, m)$$$. The robot moves in steps: at each step, it can move one unit to the right or one unit up. In other words, if it is currently at point $$$(i, j)$$$, it can move to either $$$(i + 1, j)$$$ or $$$(i, j + 1)$$$ in one step.

You do not know the exact route of the robot, but you need to intercept it. For this purpose, you have a jammer with power $$$r$$$, which you can place at any integer point $$$(x, y)$$$ on the field ($$$0 \le x \le n$$$; $$$0 \le y \le m$$$).

The robot is considered to be intercepted if at some point during its movement it is within a distance of no more than $$$r$$$ from the jammer. In other words, if there exists a point $$$(i, j)$$$ on the robot's path such that $$$\sqrt{(i - x)^2 + (j - y)^2} \le r$$$.

Image

But there is a problem: if you place the jammer too close to the starting or the ending point of the robot's route, it will be noticed, and your plan will be compromised. Thus, you want to position the jammer so that it covers neither the point $$$(0, 0)$$$ nor the point $$$(n, m)$$$ (i. e., the distance to each of them must be strictly greater than $$$r$$$).

Calculate the number of suitable points for placing the jammer. A point is suitable if it is not too close to the ends of the route, but at the same time, the robot will be intercepted regardless of the route it takes.

Input

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

The first and only line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$r$$$ ($$$n, m \ge 1$$$; $$$n \cdot m \le 10^9$$$; $$$1 \le r \le n + m$$$) — the dimensions of the field and the power of the jammer.

Output

For each test case, output a single integer — the number of points suitable for placing the jammer.

Example
Input
6
1 1 1
10 5 3
3 6 3
4 2 3
1000000000 1 2
1 1000000000 499999999
Output
0
16
6
0
1999999992
4
Note

One possible placement of the jammer for the second test case is illustrated in the statement.

H. Sum of MEX
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The MEX of a sequence of non-negative integers $$$[s_1, s_2, \dots, s_n]$$$ is the smallest non-negative integer that does not appear in this sequence.

Given an array $$$[a_1, a_2, \dots, a_n]$$$, where each element is an integer from $$$-1$$$ to $$$n$$$. For each $$$i$$$ from $$$1$$$ to $$$n$$$, calculate $$$f([a_1, a_2, \dots, a_i])$$$, where $$$f(s)$$$ for an array $$$s$$$ is defined as follows:

  • consider all distinct arrays $$$s'$$$ that can be obtained from the array $$$s$$$ by replacing all elements equal to $$$-1$$$ with integers from $$$0$$$ to $$$n$$$;
  • $$$f(s)$$$ is the sum of the MEX of all such arrays $$$s'$$$.
Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-1 \le a_i \le n$$$).

An additional constraint on the input: the array $$$a$$$ contains no more than $$$300$$$ elements equal to $$$-1$$$.

Output

For each $$$i$$$ from $$$1$$$ to $$$n$$$, output a single integer — $$$f([a_1, a_2, \dots, a_i])$$$, taken modulo $$$998244353$$$.

Examples
Input
5
-1 1 -1 3 -1
Output
1 2 24 26 248
Input
7
3 5 -1 -1 -1 -1 1
Output
0 0 1 17 223 2645 4906
Input
10
3 8 5 1 0 0 7 2 2 8
Output
0 0 0 0 2 2 2 4 4 4
Note

Consider $$$i=3$$$ in the first example. We need to calculate $$$f([-1, 1, -1])$$$. There are $$$36$$$ different arrays that can be obtained by replacing each element $$$-1$$$ with an integer from $$$0$$$ to $$$5$$$. For $$$25$$$ of them (those that do not contain $$$0$$$), the MEX is $$$0$$$. Let's consider the remaining $$$11$$$:

  • The MEX of the array $$$[0, 1, 0]$$$ is $$$2$$$;
  • The MEX of the array $$$[0, 1, 1]$$$ is $$$2$$$;
  • The MEX of the array $$$[0, 1, 2]$$$ is $$$3$$$;
  • The MEX of the array $$$[0, 1, 3]$$$ is $$$2$$$;
  • The MEX of the array $$$[0, 1, 4]$$$ is $$$2$$$;
  • The MEX of the array $$$[0, 1, 5]$$$ is $$$2$$$;
  • The MEX of the array $$$[1, 1, 0]$$$ is $$$2$$$;
  • The MEX of the array $$$[2, 1, 0]$$$ is $$$3$$$;
  • The MEX of the array $$$[3, 1, 0]$$$ is $$$2$$$;
  • The MEX of the array $$$[4, 1, 0]$$$ is $$$2$$$;
  • The MEX of the array $$$[5, 1, 0]$$$ is $$$2$$$.

The sum of these values is $$$24$$$.

If we consider $$$i=4$$$, then we need to append $$$3$$$ to each of these arrays. This will increase the MEX of two arrays by $$$2$$$, so for $$$i=4$$$, the answer is $$$26$$$.

I. Strange Process
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given three arrays:

  • array $$$a$$$, initially consisting of $$$n$$$ ones;
  • array $$$b$$$, initially consisting of $$$m$$$ zeros;
  • array $$$c$$$, consisting of $$$m$$$ integers from $$$1$$$ to $$$50$$$.

We perform the following process on these arrays. The process consists of $$$m$$$ stages. During the $$$i$$$-th stage, the following occurs:

  1. first, for each element of the array $$$a$$$, one of three actions is independently chosen: it is multiplied by some prime number, divided by some prime number (it cannot be divided by a number that does not divide the element evenly), or remains unchanged. You don't have to choose the same action or prime number for each element of $$$a$$$;
  2. then you can either skip this step or choose any $$$k$$$ such that $$$a_k = c_i$$$, and assign $$$b_i = k$$$.

An array of $$$m$$$ numbers from $$$0$$$ to $$$n$$$ is called achievable if it can be obtained as a result of this process as the array $$$b$$$.

Your task is to count the number of achievable arrays.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^4$$$).

The second line contains $$$m$$$ integers $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_i \le 50$$$).

Output

Print one integer — the number of achievable arrays, taken modulo $$$998244353$$$.

Examples
Input
4 3
4 2 3
Output
21
Input
2 4
1 2 3 4
Output
51
Input
1 2
47 34
Output
3