JUST Individuals Programming Contest 2026
A. Tree Partition
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a sequence $$$a$$$ of $$$n$$$ positive integers.

Each integer represents the maximum number of connections a node can have.

You have to partition the sequence into the minimum possible number of non-empty subsequences.

Each element must belong to exactly one subsequence.

A subsequence is called valid if its elements can form a connected rooted tree such that:

  • the first element of the subsequence is the root;
  • every child appears after its parent in the subsequence;
  • for every node, the number of edges connected to it does not exceed its value.

Your task is to find the minimum number of valid subsequences needed to partition the given sequence.

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 length of the sequence.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the maximum number of connections each node can have.

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 — the minimum number of valid subsequences needed to partition the given sequence.

Example
Input
3
3
2 1 1
2
1 1
6
2 1 3 1 1 2
Output
1
1
2
Note

B. Concatenation Pairs
time limit per test
3.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ positive integers.

You are also given an integer $$$k$$$.

For two integers $$$x$$$ and $$$y$$$, let $$$\mathrm{concat}(x, y)$$$ be the integer formed by writing $$$x$$$ followed by $$$y$$$ in decimal representation.

For example, $$$\mathrm{concat}(120, 45) = 12045$$$.

Your task is to count the number of ordered pairs $$$(i, j)$$$ such that $$$\mathrm{concat}(a_i, a_j)$$$ is divisible by $$$k$$$.

The order of the pair matters. Also, it is allowed that $$$i = j$$$.

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 two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) — the length of the array and the required divisor.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^8$$$).

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 — the number of ordered pairs $$$(i, j)$$$ such that $$$\mathrm{concat}(a_i, a_j)$$$ is divisible by $$$k$$$.

Example
Input
3
3 3
1 2 3
2 11
1 10
4 5
5 10 2 3
Output
3
2
8

C. Power Comparison
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integers $$$a$$$ and $$$b$$$.

Your task is to compare the values of $$$a^b$$$ and $$$b^a$$$.

Here, $$$x^y$$$ means $$$x$$$ raised to the power of $$$y$$$.

For each test case, determine whether $$$a^b$$$ is greater than, equal to, or less than $$$b^a$$$.

Input

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

The first and only line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^9$$$).

Output

For each test case, print a single character:

  • print > if $$$a^b \gt b^a$$$;
  • print = if $$$a^b = b^a$$$;
  • print < if $$$a^b \lt b^a$$$.
Example
Input
5
3 5
4 3
10 10
1 999
999 1
Output
>
<
=
<
>

D. Awkward Middle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$.

You can perform the following operation any number of times, possibly zero:

Choose an index $$$i$$$ such that $$$1 \lt i \lt |a|$$$ and $$$a_{i-1} = a_{i+1}$$$, then remove the $$$i$$$-th element from the array.

Here, $$$|a|$$$ denotes the current length of the array.

Your task is to find the minimum possible length of the array after performing the operation any number of times.

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 length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 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, print a single integer — the minimum possible length of the array after performing the operation any number of times.

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

In the first test case, one possible sequence of operations is:

$$$$$$ [1, 2, 1, 3, 1] \rightarrow [1, 1, 3, 1] \rightarrow [1, 1, 1] \rightarrow [1, 1] $$$$$$

So the minimum possible length is $$$2$$$.

In the second test case, no operation can be performed, so the answer is $$$4$$$.

In the third test case, the array can be reduced to length $$$3$$$.

E. XOR to Zero
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ non-negative integers.

You want to make all elements of the array equal to $$$0$$$.

In one operation, you can choose an index $$$i$$$ ($$$1 \le i \le n$$$). Let $$$S$$$ be the XOR of all elements $$$a_j$$$ such that $$$a_j \ne a_i$$$.

If there is no such index $$$j$$$, then $$$S = 0$$$.

After that, you replace $$$a_i$$$ with $$$S$$$.

Your task is to determine the minimum number of operations needed to make all elements equal to $$$0$$$.

If it is impossible, print $$$-1$$$.

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 length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \lt 2^{30}$$$).

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 — the minimum number of operations needed to make all elements equal to $$$0$$$, or $$$-1$$$ if it is impossible.

Example
Input
3
5
1 2 3 4 5
1
0
2
7 7
Output
-1
0
2

F. Keys and Doors
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n+1$$$ rooms arranged in a line, numbered from $$$1$$$ to $$$n+1$$$ from left to right.

There are also $$$n$$$ doors numbered from $$$1$$$ to $$$n$$$, where the $$$i$$$-th door connects rooms $$$i$$$ and $$$i+1$$$.

Each door $$$i$$$ has an associated non-negative integer $$$a_i$$$.

For each $$$1 \le i \le n$$$, room $$$i$$$ initially contains $$$s_i$$$ keys.

At the beginning of the $$$0$$$-th second, you are in room $$$1$$$, and all doors are closed.

For each $$$k \ge 0$$$, the following events happen in order during the $$$k$$$-th second:

  • At the beginning of the $$$k$$$-th second, all doors $$$j$$$ such that $$$a_j = k$$$ open automatically.
  • Suppose you are currently in room $$$i$$$.
    • If you are not carrying a key and there is at least one key in room $$$i$$$, you may pick up one key from this room.
    • If you are carrying a key, you may drop it in room $$$i$$$.
  • At the end of the $$$k$$$-th second:
    • You may move to room $$$i+1$$$. If door $$$i$$$ is still closed, you must be carrying a key to move through it. The key will be consumed, and door $$$i$$$ will open.
    • You may move to room $$$i-1$$$ if $$$i \gt 1$$$.
    • You may stay in room $$$i$$$.

Any door, no matter how it was opened, remains open forever.

At any moment, you may carry at most one key.

During the process, multiple keys may be placed in the same room.

Your task is to find the minimum number of seconds required to reach room $$$n+1$$$.

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 number of doors.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the integers associated with the doors.

The third line of each test case contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$0 \le s_i \le 10^9$$$) — the number of keys initially located in each room.

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 — the minimum number of seconds required to reach room $$$n+1$$$.

Example
Input
4
1
0
0
1
5
0
3
4 1 10
1 0 0
5
100 100 100 100 100
2 0 0 0 0
Output
1
6
7
103
Note

In the first test case, door $$$1$$$ opens automatically at the beginning of the $$$0$$$-th second. You can move to room $$$2$$$ at the end of the $$$0$$$-th second, so you reach room $$$2$$$ after $$$1$$$ second.

In the second test case, door $$$1$$$ opens automatically at the beginning of the $$$5$$$-th second. You can move to room $$$2$$$ at the end of the $$$5$$$-th second, so you reach room $$$2$$$ after $$$6$$$ seconds.

In the third test case, you can pick up the key in room $$$1$$$ and wait until door $$$1$$$ opens automatically at the beginning of the $$$4$$$-th second.

At the end of the $$$4$$$-th second, you move to room $$$2$$$, so you reach room $$$2$$$ after $$$5$$$ seconds.

Door $$$2$$$ has already opened automatically at the beginning of the $$$1$$$-st second, so you can move to room $$$3$$$ without using the key.

After that, you are in room $$$3$$$ after $$$6$$$ seconds, and you are still carrying the key. You can use it to open door $$$3$$$ and move to room $$$4$$$.

Therefore, you reach room $$$4$$$ after $$$7$$$ seconds.

G. Rocket Dust
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ rockets on a straight line.

The $$$i$$$-th rocket starts at position $$$x_i$$$, has direction $$$d_i$$$, and speed $$$v_i$$$.

The direction $$$d_i$$$ is either L or R. If $$$d_i = \texttt{L}$$$, the rocket moves to the left. If $$$d_i = \texttt{R}$$$, the rocket moves to the right.

It is guaranteed that all starting positions are distinct.

At the beginning, the rockets are not moving. At time $$$0$$$, Moon presses a dangerous button, and all rockets start moving at the same time.

If at the same moment two or more rockets are at the same position, all of these rockets explode into dust. After a rocket explodes, it disappears and will not affect any other rocket.

For each rocket, determine the time at which it explodes, or determine that it will never explode.

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 number of rockets.

The second line of each test case contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$0 \le x_i \le 10^9$$$) — the starting positions of the rockets.

The third line of each test case contains a string $$$d$$$ of length $$$n$$$ ($$$d_i \in \{\texttt{L}, \texttt{R}\}$$$) — the directions of the rockets.

The fourth line of each test case contains $$$n$$$ integers $$$v_1, v_2, \dots, v_n$$$ ($$$1 \le v_i \le 10^9$$$) — the speeds of the rockets.

It is guaranteed that all $$$x_i$$$ are distinct.

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 one line containing $$$n$$$ values.

The $$$i$$$-th value should be the explosion time of the $$$i$$$-th rocket.

If the rocket never explodes, print $$$-1$$$.

Otherwise, print the explosion time as a real number.

Your answer will be considered correct if its relative error does not exceed $$$10^{-6}$$$.

Example
Input
3
4
0 4 10 12
RLLR
1 1 2 1
3
0 4 6
RLL
1 1 2
2
0 5
RL
2 1
Output
2.0000000000 2.0000000000 -1 -1
2.0000000000 2.0000000000 2.0000000000
1.6666666667 1.6666666667
Note

In the first test case, the first rocket moves to the right with speed $$$1$$$, and the second rocket moves to the left with speed $$$1$$$.

They meet at position $$$2$$$ after $$$2$$$ seconds, so both of them explode at time $$$2$$$.

The third rocket moves to the left, and the fourth rocket moves to the right. They never meet, so both of them do not explode.

In the second test case, after $$$2$$$ seconds, all three rockets are at position $$$2$$$.

Therefore, all of them explode at time $$$2$$$.

In the third test case, the first rocket moves to the right with speed $$$2$$$, and the second rocket moves to the left with speed $$$1$$$.

They meet after $$$\frac{5}{3}$$$ seconds, so both of them explode at time $$$\frac{5}{3}$$$.

H. Prefix MEX
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$a$$$ and $$$b$$$ of non-negative integers.

The array $$$a$$$ has length $$$n$$$, and the array $$$b$$$ has length $$$m$$$.

You are also given an integer $$$k$$$.

You have to choose a non-empty prefix of $$$a$$$ and a non-empty prefix of $$$b$$$.

Let $$$S$$$ be the set of all values that appear in the two chosen prefixes.

Your task is to determine whether it is possible to choose the two prefixes such that $$$\mathrm{mex}(S) = k$$$.

The $$$\mathrm{mex}$$$ of a set is the smallest non-negative integer that does not belong to the set.

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 three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$, $$$0 \le k \le 10^9$$$) — the length of array $$$a$$$, the length of array $$$b$$$, and the required MEX, respectively.

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

The third line of each test case contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$0 \le b_i \le 10^9$$$).

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

Output

For each test case, print YES if it is possible to choose a non-empty prefix of $$$a$$$ and a non-empty prefix of $$$b$$$ such that the MEX of the set of chosen values is equal to $$$k$$$.

Otherwise, print NO.

You can print each letter in any case. For example, YES, Yes, and yes will all be accepted.

Example
Input
4
3 3 2
0 7 5
1 8 9
3 2 2
0 2 1
3 4
2 3 0
5 6
7 8 9
4 3 3
0 1 2 4
5 6 7
Output
YES
NO
YES
YES

I. AAA
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$S$$$ of length $$$n$$$.

The string $$$S$$$ consists only of the character 'A'.

Your task is to count how many substrings of $$$S$$$ are equal to "AAA".

A substring is a contiguous part of the string.

Input

The first and only line contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the length of the string $$$S$$$.

It is guaranteed that $$$S$$$ consists of exactly $$$n$$$ characters, and all of them are equal to 'A'.

Output

Print a single integer — the number of substrings of $$$S$$$ that are equal to "AAA".

Examples
Input
5
Output
3
Input
1
Output
0
Note

For $$$n = 5$$$, the string is "AAAAA".

The substrings equal to "AAA" start at positions $$$1$$$, $$$2$$$, and $$$3$$$, so the answer is $$$3$$$.

J. Safe Ride
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The final match of the World Cup will be played between Jordan and Argentina.

The tickets are already sold. Jordan will have $$$A$$$ supporters, and Argentina will have $$$B$$$ supporters.

Now, all supporters need to go to the stadium. There are two types of vehicles available:

  • a bus can carry at most $$$25$$$ supporters;
  • a taxi can carry at most $$$4$$$ supporters.

However, supporters of different teams cannot be placed in the same vehicle, because this will cause a problem.

You are given $$$A$$$, $$$B$$$, $$$x$$$, and $$$y$$$, where $$$x$$$ is the number of available buses and $$$y$$$ is the number of available taxis.

Determine whether it is possible to transport all supporters to the stadium without putting supporters of different teams in the same vehicle.

A vehicle does not have to be full. It is allowed for a vehicle to carry only one supporter.

Input

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

The first and only line of each test case contains four integers $$$A$$$, $$$B$$$, $$$x$$$, and $$$y$$$ ($$$1 \le A, B \le 10^9$$$, $$$0 \le x, y \le 10^9$$$) — the number of Jordan supporters, the number of Argentina supporters, the number of available buses, and the number of available taxis, respectively.

Output

For each test case, print YES if it is possible to transport all supporters to the stadium without causing problems.

Otherwise, print NO.

You can print each letter in any case. For example, YES, Yes, and yes will all be accepted.

Example
Input
6
25 4 1 1
26 4 1 1
30 20 2 3
50 50 3 0
1 1 0 1
100 1 4 1
Output
YES
NO
YES
NO
NO
YES
Note

In the first test case, we can put the $$$25$$$ Jordan supporters in the bus, and the $$$4$$$ Argentina supporters in the taxi.

In the second test case, the $$$26$$$ Jordan supporters need both the bus and the taxi, so there will be no vehicle left for the Argentina supporters.

In the fifth test case, there is only one taxi. Although it has enough capacity for two people, it cannot carry supporters from both teams.