GJU JCPC Qualification 2026
A. Three people walked into GJU
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sami, Void, and Moon were bored on a random Friday night, so they decided to go to GJU. Print how many people decided to go to GJU.

Input

no input

Output

output 3

Example
Input
no input
Output
3

B. Aziz Teams Qualifications
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

GJU is hosting its qualification contest to select the best teams to represent the university at the Jordanian Collegiate Programming Contest (JCPC).

There are $$$n$$$ teams participating, and the $$$i$$$-th team solved $$$a_i$$$ problems during the contest. Aziz, the contest director, has set a strict qualification rule: a team will qualify for the JCPC if and only if they solved strictly more than $$$x$$$ problems.

Your task is to help Aziz calculate exactly how many teams have qualified for the JCPC.

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 $$$x$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le x \le 20$$$) — the number of teams and the qualification threshold.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 20$$$) — the number of problems solved by each team.

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 a single integer — the total number of teams that qualified for the JCPC.

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

C. Void's Batteries
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two arrays $$$charge$$$ and $$$capacity$$$, both of size $$$n$$$, where $$$charge_i$$$ represents the initial amount of charge in battery $$$i$$$, and $$$capacity_i$$$ represents its maximum capacity ($$$0 \le charge_i \le capacity_i$$$).

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

  • Transfer $$$1$$$ integer unit of charge from battery $$$i$$$ to battery $$$j$$$ ($$$i \neq j$$$).

You cannot transfer charge into a battery if it would cause its charge to exceed its capacity.

Find the maximum possible number of fully charged batteries.

Note: A battery is fully charged when its charge is equal to its capacity.

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 batteries.

The following $$$n$$$ lines each contain two integers $$$charge_i$$$ and $$$capacity_i$$$ ($$$0 \le charge_i \le capacity_i \le 10^9$$$) — the initial charge and capacity of the $$$i$$$-th battery.

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 a single integer — the maximum possible number of fully charged batteries after performing the operations optimally.

Example
Input
3
3
1 4
2 3
1 5
5
5 6
5 6
5 6
5 6
5 6
1
13 1000000000
Output
1
4
0

D. Abushogi's Revenge (Easy version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The difference between the versions is that in this version, you need to construct an initial game state that results in a draw.

Since MrMoon didn't mention abushogi in the editorial last time, he decided to take his revenge.

To settle the score, abushogi and void decided to play a game. There are $$$n$$$ wallets of Moons lined up on a table. The $$$i$$$-th wallet initially contains $$$a_i$$$ dollars ($$$a_i \ge 1$$$).

The game is played in turns, with abushogi taking the first turn (Turn 1), void taking Turn 2, and so on.

On a player's turn, they can repeatedly choose any non-empty wallet and take at least one dollar from it. A player's turn only ends immediately when the wallet they last took money from reaches exactly $$$0$$$ dollars.

Both players play optimally to maximize their own total amount of money.

Your task is to construct an array $$$a$$$ of $$$n$$$ integers ($$$1 \le a_i \le 10^9$$$) representing the initial amounts in the wallets such that if both players play optimally, the game ends in a draw (both players finish with the exact same amount of money).

Input

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

The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of wallets.

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

Output

For each test case:If it is impossible to end the game in a draw, output -1.

Otherwise, output $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the initial amounts of dollars in the wallets.

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

E. Abushogi's Revenge (Mid version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Since MrMoon didn't mention abushogi in the editorial last time, he decided to take his revenge.

To settle the score, abushogi and void decided to play a game.There are $$$n$$$ wallets of Moons lined up on a table.

The $$$i$$$-th wallet initially contains $$$a_i$$$ dollars. The game is played in turns, with abushogi taking the first turn (Turn 1), void taking Turn 2, abushogi taking Turn 3, and so on.

On a player's turn, they choose exactly one available wallet on the table, take all the money inside it, and their turn immediately ends. The chosen wallet is then removed from the table.

Both players play optimally to maximize their own total amount of money. Given the initial amounts in the wallets, you need to determine the exact amount of money abushogi and void will each have at the end of turn $$$k$$$. If all wallets are taken before turn $$$k$$$, the game ends early, and you should output their final scores.

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 number of wallets and the requested turn number.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the initial amount of dollars in each wallet.

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 two integers: the amount of money abushogi has, and the amount of money void has, respectively, at the end of turn $$$k$$$.

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

In the first test case, $$$k=1$$$. Abushogi takes the first turn. To maximize his money, he chooses the wallet with $$$5$$$ dollars. Void hasn't played yet. The scores are $$$5$$$ and $$$0$$$.

In the second test case, $$$k=3$$$. Abushogi takes the $$$5$$$, void takes the $$$3$$$, and abushogi takes the $$$2$$$. Total scores are $$$7$$$ and $$$3$$$.

F. Abushogi's Revenge (Hard version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Since MrMoon didn't mention abushogi in the editorial last time, he decided to take his revenge.

To settle the score, abushogi and void decided to play a game.

There are $$$n$$$ wallets of Moons lined up on a table. The $$$i$$$-th wallet initially contains $$$a_i$$$ dollars.

The game is played in turns, with abushogi taking the first turn (Turn 1), void taking Turn 2, and so on. On a player's turn, they can repeatedly choose any non-empty wallet and take at least one dollar from it. A player's turn only ends immediately when the wallet they last took money from reaches exactly $$$0$$$ dollars.

Both players play optimally to maximize their own total amount of money. Given the initial amounts in the wallets, you need to determine the exact amount of money abushogi and void will each have at the end of turn $$$k$$$. If the game ends before turn $$$k$$$, output their final scores.

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 number of wallets and the turn number you are querying.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the initial amount of dollars in each wallet.

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 two integers: the amount of money abushogi has, and the amount of money void has, respectively, at the end of turn $$$k$$$.

Example
Input
3
3 1
5 2 3
3 3
5 2 3
4 2
1 1 1 1
Output
8 0
9 1
1 1

G. Void and Moon's Brainrot
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Moon has $$$S$$$ minutes remaining before his flight and wants to sleep for at least $$$x$$$ minutes.

His friend Void sends him $$$n$$$ reels, where the $$$i$$$-th reel takes $$$s_i$$$ minutes to watch. Moon must first watch all $$$n$$$ reels, and then reply to each one with a reel of the exact same duration.

To find these replies, Moon opens his own feed containing $$$m$$$ reels, where the $$$j$$$-th reel takes $$$b_j$$$ minutes to watch. He follows this exact process:

  • He watches the reels in his feed sequentially, starting from $$$j = 1$$$ without skipping any;
  • If the current reel $$$b_j$$$ matches the duration of an unanswered reel from Void, he pairs them up. (If Void sent multiple reels of the same duration, Moon must find a distinct matching reel for each one).
  • He stops watching his feed the exact moment he successfully finds a match for all $$$n$$$ of Void's reels.

Determine if Moon's feed contains all $$$n$$$ necessary replies AND if his total time spent watching reels (both Void's and his own) leaves him with at least $$$x$$$ minutes remaining to sleep.

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 four integers $$$n$$$, $$$m$$$, $$$x$$$, and $$$S$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$, $$$1 \le x \le S \le 10^{14}$$$) — the number of reels Void sent, the number of reels on Moon's feed, the required minutes of sleep, and the total minutes remaining until the flight.

The second line of each test case contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$1 \le s_i \le 10^9$$$) — the duration of each reel sent by Void, in minutes.

The third line of each test case contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 10^9$$$) — the duration of each reel on Moon's feed, in minutes.

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

Output

For each testcase print "YES" (without quotes) if Moon can successfully find all matching reels and have at least $$$x$$$ minutes remaining to sleep.

Otherwise, print "NO". This includes situations where Moon does not have enough time, as well as situations where it is impossible to find all required matching reels in his feed.

the "YES"s and "NO"s are case-insensitive, meaning that outputs such as "yEs" and "nO" are valid. However, the grid is case-sensitive.

Example
Input
5
3 5 60 100
5 2 5
1 5 2 3 5
1 3 10 20
10
1 2 3
2 3 60 70
5 5
5 5 5
1 1 30 40
5
5
2 4 10 100
3 3
3 1 2 4
Output
YES
NO
NO
YES
NO

H. Moon's Forgotten Order
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Abushogi owns a famous restaurant that serves exactly $$$n$$$ dishes. The dishes are listed in a menu and are indexed from $$$1$$$ to $$$n$$$.

Void asked Moon to order a specific dish from the menu. However, by the time Moon reached the counter, he had completely forgotten the name of the dish!

The only thing Moon remembers is a mathematical clue about the 1-based index of the dish: he remembers that the index $$$i$$$ satisfies the equation $$$i \bmod x = y$$$.

Given the names of the $$$n$$$ dishes on Abushogi's menu, help Moon by outputting the names of all the possible dishes that Void might have asked for, in the order they appear on the menu. If no dish in the menu satisfies this condition, output 0.

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$$$, $$$x$$$, and $$$y$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le x \le 10^9$$$, $$$0 \le y \lt x$$$) — the number of dishes, the modulo, and the remainder.

The second line of each test case contains $$$n$$$ strings — the names of the dishes. Each string consists only of lowercase English letters and has a length between $$$1$$$ and $$$10$$$.

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 the names of all possible dishes separated by a space. If there are no such dishes, output 0.

Example
Input
4
5 2 1
sushi ramen tempura udon mochi
4 3 0
pizza burger pasta salad
3 10 5
steak ribs chicken
5 1 0
a b c d e
Output
sushi tempura mochi 
pasta 
0
a b c d e
Note

In the first testcase, indices 1, 3, and 5 modulo 2 equal 1.

In the second case, only 3 works

I. Chef Abushogi cooking
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Chef Abushogi is making his signature turkey and cheese sandwiches. A perfect sandwich requires exactly 4 ingredients in a strict specific order: a slice of Bread, then Turkey, then Cheese, and finally another slice of Bread.

You are given a string $$$S$$$ representing the ingredients available on the kitchen counter from left to right. The string consists only of the characters:

  • 'b' representing Bread;
  • 't' representing Turkey;
  • 'c' representing Cheese;

To make a sandwich, you must select 4 characters from the string such that their indices $$$i_1 \lt i_2 \lt i_3 \lt i_4$$$ correspond exactly to the sequence "btcb". Each character in the string can be used in at most one sandwich.

Find the maximum number of perfect sandwiches Chef Abushogi can make.

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 string $$$S$$$.

The second line of each test case contains the string $$$S$$$ of length $$$n$$$, consisting only of the characters 'b', 't', and 'c'.

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 a single integer — the maximum number of perfect sandwiches that can be formed.

Example
Input
5
8
btcbbtcb
6
btctcb
7
bbttccb
4
tbcb
10
bbbtcbttcb
Output
2
1
1
0
2
Note

In the second case btctcb, we can form one sandwich using indices 1, 2, 3, 6. In the third case bbttccb, we can form one sandwich using indices 2, 3, 5, 7

J. MrMoon's Gaming Setup
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

MrMoon is organizing a massive competitive programming and gaming tournament.

To set up the gaming stations, he needs to assemble complete gamepads. A complete gamepad set consists of exactly one Left Controller and exactly one Right Controller.Currently, MrMoon has counted $$$x$$$ Left Controllers and $$$y$$$ Right Controllers in his inventory.

Determine the maximum number of complete gamepad sets MrMoon can assemble for the tournament.

Input

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

Each test case consists of a single line containing two integers $$$x$$$ and $$$y$$$ ($$$0 \le x, y \le 10^{18}$$$) — the number of Left Controllers and the number of Right Controllers, respectively.

Output

For each test case, output a single integer — the maximum number of complete gamepad sets possible.

Example
Input
4
5 3
10 10
0 5
1000000000000000000 999999999999999999
Output
3
10
0
999999999999999999

K. Abushogi's Happy Name
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Abushogi has recently picked up a fascinating new hobby: analyzing people's names mathematically.First, he takes a person's name (which consists only of lowercase English letters) and converts each character into a number based on its position in the alphabet.

Specifically, 'a' becomes $$$1$$$, 'b' becomes $$$2$$$, 'c' becomes $$$3$$$, and so on, up to 'z' which becomes $$$26$$$. Then, he calculates the product of all these numbers.

Abushogi will be happy if the resulting product is divisible by $$$6$$$. Given a name, determine if Abushogi will be happy.

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 10^5$$$) — the length of the name.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters — the name Abushogi is analyzing.

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 "YES" if Abushogi will be happy, and "NO" otherwise.

In the output, the "YES"s and "NO"s are case-insensitive, meaning that outputs such as "yEs" and "nO" are valid. However, the grid is case-sensitive.

Example
Input
5
3
abc
4
moon
2
ac
5
aaaaa
4
code
Output
YES
YES
NO
NO
YES
Note

Note: In the first testcase, 'a'=1, 'b'=2, 'c'=3. The product is 6, which is divisible by 6.

In the third testcase, 'a'=1, 'c'=3. The product is 3, which is not divisible by 6. In the fourth testcase, the product is 1

L. Abushogi's Escape
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Abushogi is trying to run away from the police. The city he is in can be represented as a tree consisting of $$$n$$$ intersections (nodes) and $$$n-1$$$ bidirectional roads (edges).

Abushogi is currently at the root of the tree, which is intersection $$$1$$$. He will successfully escape and be considered safe if he can reach any leaf intersection in the city.

An intersection is considered a leaf if it is connected to exactly one other intersection (and is not intersection $$$1$$$).

If the city only has $$$1$$$ intersection, intersection $$$1$$$ is considered a leaf. However, the police have deployed cops at certain intersections. Abushogi cannot pass through or land on any intersection that has a cop stationed there.

If there is a cop at intersection $$$1$$$, Abushogi is instantly caught.Given the layout of the city and the locations of the cops, determine if it is possible for Abushogi to reach a leaf intersection and escape.

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 intersections.

The second line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$c_i \in \{0, 1\}$$$). If $$$c_i = 1$$$, there is a cop at intersection $$$i$$$. If $$$c_i = 0$$$, intersection $$$i$$$ is empty.Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n, u \ne v$$$) — representing a bidirectional road between intersection $$$u$$$ and intersection $$$v$$$.

It is guaranteed that the given edges form a valid tree, and the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output "YES" if it is possible for Abushogi to reach a leaf intersection without encountering any cops. Otherwise, output "NO".

In the output, the "YES"s and "NO"s are case-insensitive, meaning that outputs such as "yEs" and "nO" are valid. However, the grid is case-sensitive.

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

In the first testcase, intersection 3 has a cop. Abushogi can run $$$1 \rightarrow 2 \rightarrow 4$$$ or $$$1 \rightarrow 2 \rightarrow 5$$$ to escape.

In the second testcase, there is a cop at intersection 1, so he is instantly caught. In the third testcase, the city only has 1 intersection, and it's empty, so he is already safe.

M. Tardi's and Sami's Ten Little Monkeys
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ beds perfectly aligned in a row, numbered from $$$1$$$ to $$$n$$$.You are taking care of $$$m$$$ monkeys.

Each monkey has a specific jump power, where the $$$i$$$-th monkey has a jump power of $$$a_i$$$. All monkeys start on the floor at position $$$0$$$ (strictly before the first bed).

You can allow the monkeys to jump on the beds one by one, in any order you choose. When the $$$i$$$-th monkey is allowed to jump, it will take leaps of exactly $$$a_i$$$ distance forward. This means the monkey will land on bed $$$a_i$$$, then bed $$$2a_i$$$, then bed $$$3a_i$$$, and so on, until it jumps past the $$$n$$$-th bed.

The beds are fragile. If any monkey lands on a bed, the bed instantly breaks. Once a bed is broken, it remains broken. Multiple monkeys can land on the same broken bed.Determine the total number of beds that will be broken after you let all $$$m$$$ monkeys jump.

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 $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — the number of beds and the number of monkeys.

The second line contains $$$m$$$ integers $$$a_1, a_2, \ldots, a_m$$$ ($$$2 \le a_i \le n$$$) — the jump power of each monkey.

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

Output

For each test case, output a single integer — the total number of broken beds.

Example
Input
4
10 2
4 6
5 3
2 3 4
100 1
50
6 4
2 2 2 2
Output
3
3
2
3