ACPC Kickoff 2021
A. Sakally Soldier
time limit per test
2 seconds
memory limit per test
256 megabytes
input
alimagde.in
output
standard output

Khaled is a sakally soldier. A sakally soldier is a soldier too lazy to do any duties during his service in the military.

One day during the morning assembly Sergeant Magde decided to choose some soldiers to be on duty.

The $$$N$$$ soldiers available will form a queue of $$$N$$$ positions numbered $$$1$$$ through $$$N$$$ where each soldier stands on one position.

Sergeant Magde will do the following:

When picking the $$$i^{th}$$$ soldier he will count $$$i$$$ positions starting from the last picked position (initially equal to $$$0$$$) then pick the soldier standing on that position.

Note that Sergeant Ali will only do the above operation if he can count $$$i$$$ positions.

Since Soldier Khaled is sakally, he decided to pick different positions from the ones Sergeant Ali will pick.

Your task is to help Soldier Khaled count how many different positions he can pick so that Sergeant Ali won't pick him?

Input

The first line consists of a single integer $$$T$$$ $$$(1 \leq T \leq 100)$$$, denoting the number of test cases.

Each test case contains a single integer $$$N$$$ $$$(1 \leq N \leq 10^9)$$$, denoting the number of soldiers.

Output

For each test case, print a single line containing a single integer denoting how many different positions Soldier Khaled can pick.

Example
Input
2
8
2
Output
5
1
Note

The answer of $$$8$$$ is $$$5$$$ since the picked soldiers will be $$${1, 3, 6}$$$, and then the remaining positions for Soldier Khaled are $$${2, 4, 5, 7, 8}$$$.

The answer of $$$2$$$ is $$$1$$$ since the picked soldiers will be $$${1}$$$, and then the remaining positions for Soldier Khaled are $$${2}$$$.

B. Zero equals Infinity!
time limit per test
2 seconds
memory limit per test
64 megabytes
input
polygon.in
output
standard output

Two of the judges discussed an interesting question. For a polygon with a given Perimeter P, if we want to maximize the area A, should we decrease or increase the number of sides?

After they searched on the internet, they found that the circle is the best shape to maximize A given P, but they still couldn't agree if the circle has 0 or ∞ sides.

You can't convince them just by choosing one direction. So you will write a program that takes P and a value X, find the number of sides S such that all polygons with S sides and P Perimeter have ratio not larger than but as close as possible to X where A is the area of the polygon.

If the answer is 0 output "Khairy" instead. If the answer is ∞ output "KEE" instead.

Input

The first line of the input contains one integer T (1 ≤ T ≤ 100) the number of test cases.

Each test case contains two numbers P and X (1 ≤ P ≤ 106, 1 ≤ X ≤ P). X is a fractional value with no more than 3 digit after the decimal point.

Output

For each test case, output S the number of sides of a polygon such that isn't larger than but as close as possible to X.

If the answer is 0 output "Khairy" instead. If the answer is ∞ output "KEE" instead.

Example
Input
4
50 3.975
100 7.600
40 2.000
1000000 79577.400
Output
58
8
3
1912

C. Topology vs Geometry
time limit per test
5 seconds
memory limit per test
128 megabytes
input
triangles.in
output
standard output

Many contestants fear geometry problems for reasons such as precision errors, lack of math background, or unfamiliarity with the problems. Mohammad Yasser recently learned the difference between geometry and topology and found that topology problems are more familiar to competitive programming contestants.

Geometry asks about length, area, volume, angles, and other rigid properties of the shapes. Topology asks about connections and morphology, and other properties that don't change with different transformations like bending or rotation. Mohammad Yasser created an example:

Given an array of 3D triangles, find if the triangles form a triangle mesh. A triangle mesh is a set of connected triangles. Two triangles are directly connected if they both share a side, not just a vertex.

Input

The first line of the input contains one integer T (1 ≤ T ≤ 4) the number of test cases.

The first line of each test case contains a number n (1 ≤ N ≤ 105)  -  the number of the triangles.

N lines follow, each containing 9 integers Ti (0 ≤ Ti ≤ 104) each three consecutive integers represent a vertex of the triangle.

Output

For each test case, output "Yes" if the set of triangles are connected or "No" if they aren't. The checker is case-insensitive so you can output "yEs", "nO", "yes", "NO", etc.

Examples
Input
2
3
1000 0 0 0 1000 0 0 999 52
1000 0 0 0 999 52 0 995 105
1000 0 0 0 995 105 0 988 156
3
1000 0 0 0 1000 0 0 999 52
1000 0 0 0 999 52 0 995 105
1000 0 0 0 990 105 0 988 156
Output
Yes
No
Input
2
1
723 266 256 672 193 288 983 379 275
3
806 979 348 759 807 570 341 653 449
723 266 256 983 379 275 167 354 850
678 629 730 806 979 348 768 587 581
Output
Yes
No

D. 2wix
time limit per test
5 seconds
memory limit per test
256 megabytes
input
two.in
output
standard output

Yasser is a coach in the ACPC. One day he decided to teach his trainee Khaled Hamed some basic Math. Since Khaled is ... well Khaled, Yasser needed some fun activity to teach him.

Yasser brought some 2wix chocolates with him since they have $$$2$$$ bars and gave Khaled a number $$$N$$$.

You are going to create expressions with the following operations $$$(+, -, *, /)$$$ using Parenthesis "$$$()$$$" and the number $$$2$$$ to represent the number $$$N$$$.

Please note that the operation $$$/$$$ corresponds to integer division in which the fractional part (remainder) is discarded.

For example: $$$9$$$ can be represented by at least five $$$2s$$$

$$$9 = \displaystyle ((2+2)*2)+\frac{2}{2} $$$

Khaled wanted to know if it's possible to create such an expression, and if so what the minimum number of $$$2s$$$ needed to create an expression that evaluates to $$$N$$$, so he can get the remaining chocolates.

The following part was written by Pillow:

Khaled is a blue coder so he asked you (The genius solving ACPC 2021 Kickoff Problems) to find the minimum number of $$$2s$$$ needed to represent $$$N$$$.

Note that you are allowed to use only the number $$$2$$$, you cannot use $$$22$$$, $$$222$$$, ...

Input

The first line consists of a single integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$, denoting the number of test cases.

Each test case contains a single integer $$$N$$$ $$$(0 \leq N \leq 2 \times 10^5)$$$.

Output

For each test case, print a single line containing a single integer denoting the minimum number of 2s required to represent N.

If there is no answer, print $$$-1$$$.

Example
Input
3
2
4
9
Output
1
2
5
Note

The answer of $$$2$$$ is $$$1$$$, since we have only one $$$2$$$.

The answer of $$$4$$$ is $$$2$$$, we can use either $$$(2+2)$$$ or $$$(2*2)$$$ both have only two 2s.

The answer of $$$9$$$ is $$$5$$$, one of the minimum possible expressions is $$$(((2+2)*2)+(2/2))$$$.

E. AKA AKA learns number theory
time limit per test
1.5 seconds
memory limit per test
64 megabytes
input
lcm.in
output
standard output

Some years ago, AKA AKA team lost ACPC champion title after failing to solve a number theory problem (ACPC2018 G). This year, AKA AKA team are giving you a number theory problem to prepare for the CPC.

Given an integer array A. Find an integer X between L and R that would maximize the LCM of A after inserting X in a.

Input

The first line of the input contains one integer T (1 ≤ T ≤ 100) the number of test cases.

Each test case consists of two lines:

First line contains three numbers N, L, and R (1 ≤ N ≤ 777, 1 ≤ L ≤ R ≤ 108), the length of the array and the interval for the number X.

The second line contains N integers A1, A2, ... , AN (1 ≤ Ai ≤ 108).

Output

For each test case, output one integer X (L ≤ X ≤ R) that maximizes the LCM of the array a after inserting X in a. If there are multiple answers, output the largest one.

Example
Input
2
9 1 890
1 2 3 4 5 6 7 8 9
5 1 66
2310 96577 33263 82861 190747
Output
887
64
Note

Least Common Multiple LCM of multiple arguments is computed recursively according to the equation LCM(X1, X2, ... , XN) = LCM(LCM(X1, X2, ... , XN - 1), XN).

F. Memeable String
time limit per test
7 seconds
memory limit per test
256 megabytes
input
protecting-memes.in
output
standard output

Khaled Hamed shares memes, a lot of memes, and as we all know any meme has a type represented by a lowercase Latin letter. Khaled's feed can be represented by a string S of size N where Si is the type of the ith meme he shares.

Your mission here is to rid the world of Khaled's non-funny memes. You get 2N - 1 - i IQ points for deleting the ith meme.

However, there is a string P that your teacher Pillow gave you. He told you that whatever you do S should always contain P as a subsequence.

Khaled knowing your schemes decided to protect some of his most important memes. He will present you with a binary string B such that if B[i] = 0 then you will be unable to delete the ith meme.

Can you find out the memes that should be deleted to achieve the maximum number of IQ points with P appearing in S as subsequence after the deletions?

Note that Pillow guarantees that P is initially a subsequence of S.

Input

The first line consists of a single integer T (1 ≤ T ≤ 10), denoting the number of test cases.

The first line of each test case contains two integers N and M (1 ≤ M ≤ N ≤ 2 × 105), denoting the size of S and P.

Followed by two lines containing strings S and P respectively consisting of lowercase Latin letters.

Followed by the binary string B of length N where (0 ≤ Bi ≤ 1).

Output

For each test case print a binary string ans where ansi = 1 if it's optimal to delete the ith meme.

Example
Input
2
12 6
yasserfaksan
yassan
111101010001
20 6
pileofpillsforpillow
pillow
11111111111111111111
Output
001001010000
11111111111111000000
Note

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

G. Game with Strings
time limit per test
5 seconds
memory limit per test
256 megabytes
input
game.in
output
standard output

Pillow and Khaled Hamed are playing a game with an array of strings $$$a$$$. Pillow Starts First.

Each player on his turn will choose a non-empty subset of indices $$$S$$$ such that $$$A_x = A_y$$$ and $$$1 \leq |A_x| $$$ for each $$$x$$$ and $$$y$$$ in $$$S$$$ and remove the last character from $$$A_x$$$ for all $$$x$$$ in $$$S$$$.

The player who can't make a move loses the game.

KEE the king of games deduced that if both players play optimally the winner can be decided at the beginning of the game can you find out who that winner is for our king?.

Input

The first line consists of a single integer $$$T$$$ $$$(1 \leq T \leq 100)$$$, denoting the number of test cases.

Each test case contains two lines.

On the first line, a single integer $$$N$$$ $$$(1 \leq N \leq 10^5)$$$, denoting the number of strings.

On the second line, the array $$$A$$$ where $$$(1 \leq |A_i| \leq 10^5)$$$ and $$$A_i$$$ consists only of lowercase Latin letters.

It's guaranteed that the sum of strings sizes over all test cases is $$$\leq 10^7$$$

Output

For each test case, print a single line containing the name of the winner "Pillow" or "Khaled".

Example
Input
2
10
a a abc ab abc abc bbb bbbb bbbx bbby
6
a b c d e f
Output
Khaled
Khaled

H. Annoying posts
time limit per test
1 second
memory limit per test
256 megabytes
input
bad-memes.in
output
standard output

Compo was going through his feed on FB site consisting of Khaled Hamed's posts that decrease people's IQ mixed with different posts that increase the IQ. Sick of this, Compo devised a strategy.

He will open FB at every $$$X-th$$$ minute and read all the posts he hadn't read. It's well known that Compo receives exactly one post per minute. where the $$$i-th$$$ post adds $$$A_i$$$ points to his IQ.

Considering that Compo doesn't need any time to read the posts Choose an $$$X$$$ that will maximize the minimum IQ of a single batch of posts that combo reads at once.

Input

The first line of the input contains one integer $$$T$$$ $$$(1 \leq T \leq 10)$$$ the number of test cases.

The first line of each test case contains a number $$$N$$$ $$$(1 \leq N \leq 10^5)$$$.

The second line of each test case contains an integer array $$$A_i$$$ $$$(-10^5 \leq A_i \leq 10^5)$$$.

Output

Print the maximum minimum IQ of a single batch.

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

I. Binary string
time limit per test
2 seconds
memory limit per test
64 megabytes
input
binary.in
output
standard output

Khaled Hamed challenged Compiler to solve this problem:

Given a binary string $$$S$$$ of length $$$N$$$ and an integer $$$K$$$. In one operation you can change one character that wasn't changed before. Find the minimum number of operations $$$X$$$ such that we can make every $$$S_i = S_{i+k}$$$ for all $$$(1 \leq i \leq N-K)$$$ in exactly $$$X$$$ operations.

Compiler laughed and solved the problem in one femtosecond ($$$10^{-15}$$$ second). Then Compiler challenged Khaled Hamed to solve this problem:

Given a binary string $$$S$$$ of length $$$N$$$ and an integer $$$X$$$. In one operation you can change one character that wasn't changed before. Find the minimum postive $$$K$$$ such that we can make every $$$S_i = S_{i+k}$$$ for all $$$(1 \leq i \leq N-K)$$$ in exactly $$$X$$$ operations.

It's guaranteed that each given test has a solution of less than $$$N$$$.

Input

The first line of the input contains two integers $$$N$$$ and $$$X$$$ $$$(2 \leq X \leq N \leq 2000)$$$.

The second line contains binary string $$$S$$$.

Output

Find the minimum K such that the condition is satisfied.

Examples
Input
9 6
110010011
Output
3
Input
8 4
10110100
Output
1

J. 2wix+
time limit per test
1 second
memory limit per test
256 megabytes
input
two2.in
output
standard output

Yasser is a coach in the ACPC. One day he decided to teach his trainee Khaled Hamed some basic Math. Since Khaled is ... well Khaled, Yasser needed some fun activity to teach him.

Yasser brought some 2wix chocolates with him since they have $$$2$$$ bars and gave Khaled a number $$$N$$$.

"You are going to create expressions with only one operation $$$(+)$$$ using Parenthesis "$$$()$$$" and the number $$$2$$$ to represent the number $$$N$$$".

For example: $$$8$$$ can be represented by at least 4 $$$2s$$$

$$$8 = \displaystyle ((2+2)+2+2) $$$

Khaled wanted to know if it's possible to create such an expression, and if so what the minimum number of $$$2s$$$ needed to create an expression that evaluates to $$$N$$$, so he can get the remaining chocolates.

The following part was written by Pillow:

Khaled is a blue coder so he asked you (The genius solving ACPC 2021 Kickoff Problems) to find the minimum number of $$$2s$$$ needed to represent $$$N$$$.

Note that you are allowed to use only the number $$$2$$$, you cannot use $$$22$$$, $$$222$$$, ...

Input

The first line consists of a single integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$, denoting the number of test cases.

Each test case contains a single integer $$$N$$$ $$$(0 \leq N \leq 2 \times 10^5)$$$.

Output

For each test case, print a single line containing a single integer denoting the minimum number of 2s required to represent N.

If there is no answer, print $$$-1$$$.

Example
Input
3
2
4
9
Output
1
2
-1
Note

The answer of $$$2$$$ is $$$1$$$, since we have only one $$$2$$$.

The answer of $$$4$$$ is $$$2$$$, we can use $$$(2+2)$$$.

The answer of $$$9$$$ is $$$-1$$$, since you cannot create an expression with only $$$2s$$$ and $$$+$$$ operations.

K. Helping Eagle
time limit per test
1 second
memory limit per test
256 megabytes
input
help.in
output
standard output

Your friend Eagle is playing a game.

In this game, Eagle has an array $$$A$$$ of $$$N$$$ positive integers.

In the first turn, Eagle chooses any index $$$i$$$ to start with and adds $$$A_i$$$ to his score.

Starting from the next turn, assuming that the last chosen index was index $$$i$$$. Eagle chooses any index $$$j$$$ such that $$$j$$$ wasn't chosen before and $$$|j-i| \leq 2$$$ then adds $$$A_j$$$ to his score.

Before the game starts you had a chance to choose two indices to block them such that Eagle can't choose them (at the beginning or during the game).

You would like to minimize Eagle's score if he plays optimally.

Input

The first line of the input contains one integer $$$T$$$ $$$(1 \leq T \leq 2*10^5)$$$ the number of test cases.

Each test case consists of two lines:

First line contains one number $$$N$$$ $$$(3 \leq N \leq 2 \times 10^5)$$$ the length of the array $$$n$$$.

The second line contains $$$N$$$ integers $$$A_1, A_2 \dots A_n$$$ $$$(1 \leq A_i \leq 10^9)$$$.

The total sum of $$$N$$$ over all test cases doesn't exceed $$$2 \times 10^5$$$.

Output

For each test case, output one integer, the minimum score that Eagle gets if he plays optimally.

Example
Input
2
5
1 1 1 1 1
3
10 15 4
Output
2
4

L. Memable Ace
time limit per test
1 second
memory limit per test
256 megabytes
input
max-pair.in
output
standard output

Pillow decided to give Khaled Hamed an easy problem and was surprised when Khaled Hamed solved it. Apparently, Pillow didn't know that blue coders can solve problems.

So we hope you all prove Pillow wrong by solving the given problem.

Given a string $$$S$$$ where $$$S_i \neq S_{i+1}$$$ for all $$$0 \leq i \leq |S| - 1$$$.

return the maximum distance between a pair $$$i$$$ and $$$j$$$ such that $$$i \lt j$$$ and $$$S_i \neq S_j$$$ where the distance between a pair is $$$j - i$$$.

Input

The first line contains an integer $$$T$$$ number of test cases where $$$(1 \leq T \leq 10)$$$.

The only line in each test case is the string $$$S$$$ consisting only of lowercase Latin letters where $$$(2 \leq |S| \leq 10^5)$$$.

Output

For each test case print the maximum distance between a pair satisfying the above conditions.

Example
Input
2
abcda
ababab
Output
3
5