ZU JCPC Qualification 2026
A. Hello Hello ZU
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Batata was visiting ZU for the first time, he introduced himself to the students, and asked them to print Hello Hello ZU

Input

no input

Output

print Hello Hello ZU

Example
Input
no input
Output
Hello Hello ZU

B. Hello Hello Infinite Line
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Batata gave you an infinite straight line passing through two distinct integer points $$$A(x_1, y_1)$$$ and $$$B(x_2, y_2)$$$.

Find two distinct integer points $$$C(x_3, y_3)$$$ and $$$D(x_4, y_4)$$$ such that the infinite line passing through $$$C$$$ and $$$D$$$ is strictly parallel to the line passing through $$$A$$$ and $$$B$$$ (i.e., the two lines never intersect).

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 four integers $$$x_1, y_1, x_2, y_2$$$ ($$$-1000 \le x_1, y_1, x_2, y_2 \le 1000$$$) — the coordinates of point $$$A$$$ and point $$$B$$$.

It is guaranteed that point $$$A$$$ and point $$$B$$$ are distinct (either $$$x_1 \neq x_2$$$ or $$$y_1 \neq y_2$$$).

Output

For each test case, output four integers $$$x_3, y_3, x_4, y_4$$$ ($$$-10^9 \le x_3, y_3, x_4, y_4 \le 10^9$$$) — the coordinates of point $$$C$$$ and point $$$D$$$.

The following conditions must be met:

  • Point $$$C$$$ and point $$$D$$$ must be distinct;
  • The infinite line passing through $$$C$$$ and $$$D$$$ must not intersect the infinite line passing through $$$A$$$ and $$$B$$$;
  • If there are multiple valid pairs of points, you can output any of them.
Example
Input
3
0 0 1 1
0 0 0 5
3 4 -2 1
Output
0 1 1 2
1 0 1 5
3 5 -2 2

C. Hello Hello Binary String
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$$$ of length $$$n$$$. The string is special: it contains exactly one 0 and $$$n-1$$$ 1s.

You need to process $$$q$$$ queries of the following two types:

  • $$$1$$$ $$$j$$$: Swap the single 0 with the character currently at index $$$j$$$;
  • $$$2$$$ $$$k$$$: Find and print the index of the $$$k$$$-th 1 in the string.

Assume $$$1$$$-based indexing for all string positions.

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 $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le q \le 2 \cdot 10^5$$$) — the length of the string and the number of queries.

The second line of each test case contains the binary string $$$s$$$ of length $$$n$$$.

It is guaranteed that $$$s$$$ contains exactly one 0.The following $$$q$$$ lines contain the queries. Each query is given as:

  • $$$1$$$ $$$j$$$ ($$$1 \le j \le n$$$)
  • $$$2$$$ $$$k$$$ ($$$1 \le k \le n-1$$$)

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

Output

For each query of type $$$2$$$, output a single integer representing the index of the $$$k$$$-th 1. Print the answers for type $$$2$$$ queries separated by spaces. Output a newline after each test case.

Example
Input
2
5 4
11011
2 3
1 1
2 1
2 4
3 2
011
2 2
1 3
Output
4 2 5 
3

D. Hello Hello String Mex
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

0xmar is exploring advanced string transformations. He defines the CharMex of a string as the first lowercase English letter in alphabetical order (a, b, c, ..., z) that does not appear in the string.

For example:

  • The CharMex of bca is d (since a, b, and c are present, d is the first missing letter);
  • The CharMex of xzy is a (since a is completely missing).

You are given a string $$$s$$$ of length $$$n$$$. Every character in $$$s$$$ is a lowercase English letter strictly between a and y (inclusive).

0xmar constructs a new string $$$t$$$ by calculating the CharMex for every possible contiguous substring of $$$s$$$. He appends these CharMex characters to $$$t$$$ in this exact order of substring indices $$$[i, j]$$$ (using $$$1$$$-based indexing):

  • Start at index $$$1$$$: $$$[1, 1], [1, 2], \dots, [1, n]$$$
  • Start at index $$$2$$$: $$$[2, 2], [2, 3], \dots, [2, n]$$$
  • ... Repeat this pattern until ...
  • Start at index $$$n$$$: $$$[n, n]$$$

Help 0xmar determine if the resulting string $$$t$$$ is a palindrome (reads the same forward and backward). Print YES if it is, and NO otherwise.

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 the string $$$s$$$, consisting of lowercase English letters from a to y.

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

Output

For each test case, output YES if the constructed string $$$t$$$ is a palindrome, and NO otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Example
Input
9
abc
x
ab
a
aba
bca
xay
aa
aba
Output
NO
YES
NO
YES
NO
NO
YES
YES
NO
Note

Example Visualization for abc:

Let $$$s = \text{\texttt{abc}}$$$ ($$$n = 3$$$). We calculate the CharMex for each substring:

  • Starting at index 1:
    • Segment $$$[1, 1]$$$ a $$$\rightarrow$$$ CharMex is b;
    • Segment $$$[1, 2]$$$ ab $$$\rightarrow$$$ CharMex is c;
    • Segment $$$[1, 3]$$$ abc $$$\rightarrow$$$ CharMex is d.
  • Starting at index 2:
    • Segment $$$[2, 2]$$$ b $$$\rightarrow$$$ CharMex is a;
    • Segment $$$[2, 3]$$$ bc $$$\rightarrow$$$ CharMex is a.
  • Starting at index 3:
    • Segment $$$[3, 3]$$$ c $$$\rightarrow$$$ CharMex is a.

Result: The generated string is $$$t = \text{\texttt{bcdaaa}}$$$, which is not a palindrome (NO).

E. Hello Hello Void Movies
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Void loves movies and has the ultimate home theater setup. However, this means he has to make his own popcorn—and Void is notoriously bad in the kitchen.

He has asked you to manage the tonjarah (pot) for him. You are given $$$n$$$ popcorn kernels. For the $$$i$$$-th kernel, you are given two integers: $$$P_i$$$ (the exact time it pops) and $$$B_i$$$ (the exact time it burns). A kernel is considered "perfect" if the pot is removed from the heat at time $$$T$$$ such that $$$P_i \le T \lt B_i$$$. It is guaranteed that $$$B_i \gt P_i$$$.

Find the best time $$$T$$$ to remove the pot from the heat to maximize the number of perfect popcorns for Void. If there are multiple times that yield the same maximum number of perfect popcorns, output the earliest possible time.

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

The next $$$n$$$ lines each contain two space-separated integers, $$$P_i$$$ and $$$B_i$$$ ($$$1 \le P_i \lt B_i \le 10^9$$$), representing the pop and burn times of the $$$i$$$-th kernel.

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 two space-separated integers on a new line: the maximum number of perfect popcorns, and the optimal time $$$T$$$ to remove the pot.

Example
Input
3
3
1 5
3 7
4 6
4
10 20
20 30
15 25
25 35
2
1 2
2 3
Output
3 4
2 15
1 1
Note

In the first case, at $$$T=4$$$, all three kernels are perfect (since $$$1 \le 4 \lt 5$$$, $$$3 \le 4 \lt 7$$$, and $$$4 \le 4 \lt 6$$$).

In the second case, at $$$T=15$$$, the first and third kernels are perfect. At $$$T=25$$$, the third is burned.

In the third case, they do not overlap ($$$B_1 = P_2 = 2$$$). If $$$T=2$$$, the first kernel is already burned. So max perfect is 1 at $$$T=1$$$ (or $$$T=2$$$). The earliest is $$$T=1$$$.

F. Hello Hello Addition
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Jebreel was strolling through his garden one day and decided to take up addition as a hobby for the day. Given two integers $$$a$$$ and $$$b$$$, output their sum.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$ 1 \le t \le 10^4)$$$. The description of the test cases follows.

Each test case contains a single line with two integers $$$a$$$ and $$$b$$$ ($$$0 \le a, b \le 10^{100000}$$$).

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

Output

For each test case, print a single integer — the value of $$$a + b$$$.

Example
Input
3
111 123
456 34
9 9
Output
234
490
18

G. Hello Hello Max Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Jebreel has given you an array, you should do the following operation exactly once

remove all appearances of an integer x , what is the maximum sum of the array after the operation

Input

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

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

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

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 sum of the array after applying the operation exactly once.

Example
Input
4
5
1 2 3 -1 -2
4
-5 -5 -5 -5
6
10 10 10 5 5 2
3
-1 2 -3
Output
5
0
42
1

H. Hello Hello Hyasat
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Hyasat is a dedicated software engineer who just inherited a legacy codebase. Upon running the linter, he discovers exactly $$$N$$$ warnings.To help clear the backlog, he has built two automated code-refactoring tools:

  • Quick Patch: Clears exactly $$$5$$$ warnings per run;
  • Deep Clean: Clears exactly $$$7$$$ warnings per run.

Because these tools are highly specialized, they will crash the entire system if they attempt to clear more warnings than are actually remaining.

Hyasat wants to completely eliminate all $$$N$$$ warnings using the minimum total number of tool runs.

Help him find the minimum number of times he needs to run his tools, or determine if it is impossible to clear exactly $$$N$$$ warnings without crashing the system.

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 one integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — the number of warnings in the codebase.

Output

For each test case, output a single integer: the minimum total number of tool runs required to clear exactly $$$n$$$ warnings. If it is impossible to clear the warnings exactly, output -1.

Example
Input
5
10
14
17
3
24
Output
2
2
3
-1
4

I. Hello Hello Infinite Sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Essam has recently discovered his love for arithmetic progressions. Today, he chose three positive integers $$$n$$$, $$$k$$$, and $$$l$$$.

He grabbed a marker and wrote two separate sequences on his whiteboard:

  1. The first $$$n$$$ multiples of $$$k$$$: $$$1 \cdot k, 2 \cdot k, 3 \cdot k, \dots, n \cdot k$$$.
  2. The first $$$n$$$ multiples of $$$l$$$: $$$1 \cdot l, 2 \cdot l, 3 \cdot l, \dots, n \cdot l$$$.

Essam is only interested in even numbers. He wants to find the total number of even integers written on his whiteboard across both sequences. If a number appears in both sequences, Essam writes it twice, and it should be counted twice. Given $$$n$$$, $$$k$$$, and $$$l$$$, help Essam find the total number of even integers.

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 three integers $$$n$$$, $$$k$$$, and $$$l$$$ ($$$1 \le n, k, l \le 10^9$$$).

Output

For each test case, output a single integer — the total number of even integers written on the whiteboard.

Example
Input
3
4 2 3
5 3 5
10 4 6
Output
6
4
20

J. Hello Hello Moon vs Batata
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Moon is playing a game against Batata. Moon has $$$N$$$ items. The $$$i$$$-th item has a power of $$$A_i$$$ and grants $$$C_i$$$ points if it successfully breaks Batata's $$$i$$$-th shield, which has a defense of $$$B_i$$$. Specifically, Moon earns $$$C_i$$$ points if his item's power $$$A_i \ge B_i$$$, and $$$0$$$ points otherwise.

Moon has a special ability: before the game starts, he can choose at most one of his items and change its power to exactly $$$X$$$. Batata will give Moon $$$Q$$$ independent queries.

For each query, Batata provides a modification value $$$X$$$. For each $$$X$$$, determine the maximum total points Moon can earn if he uses his special ability optimally.

Input

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

For each test case:

The first line contains two integers $$$N, Q$$$ ($$$1 \le N, Q \le 2 \cdot 10^5$$$) — denoting the number of items and queries, respectively.

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \le A_i \le 10^9$$$).

The third line contains $$$N$$$ integers $$$B_1, B_2, \ldots, B_N$$$ ($$$1 \le B_i \le 10^9$$$).

The fourth line contains $$$N$$$ integers $$$C_1, C_2, \ldots, C_N$$$ ($$$1 \le C_i \le 10^9$$$).

The next $$$Q$$$ lines each contain one integer $$$X$$$ ($$$1 \le X \le 10^9$$$) — denotes the given modification value for a query.

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

Output

For each test case, output $$$Q$$$ lines. Each line should contain one integer, representing the maximum total points Moon can earn for the given modification value $$$X$$$.

Example
Input
1
5 4
1 2 4 5 6
3 1 5 8 7
1 5 5 2 1
3
1
7
8
Output
6
5
10
10

K. Hello Hello Aziz Sort
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Moon is playing a puzzle game designed by Aziz. Aziz gives him a permutation $$$a$$$ of length $$$n$$$.Moon can perform the following three-step operation on the permutation:

  1. Choose the length $$$k$$$ of a prefix of $$$a$$$ ($$$1 \le k \le n$$$);
  2. Reverse this chosen prefix;
  3. Move the reversed prefix to the back of the permutation $$$a$$$.

For example, if the permutation is $$$[1, 10, 4, 8, 7, 3, 5, 6, 2, 9]$$$ and Moon chooses a prefix of length $$$k=4$$$, the prefix $$$[1, 10, 4, 8]$$$ is reversed to $$$[8, 4, 10, 1]$$$ and moved to the back. The new permutation becomes $$$[7, 3, 5, 6, 2, 9, 8, 4, 10, 1]$$$. Note that if $$$n$$$ is chosen as the prefix length, the operation simply reverses the entire permutation.

Moon wants to sort the permutation in ascending order. He is looking for an efficient way to solve Aziz's puzzle. Help him find a sequence of at most $$$2n$$$ operations that sorts the permutation.

It can be shown that this is always possible

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the length of the permutation $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the permutation $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test case, the first line of output should contain a single integer $$$q$$$ ($$$0 \le q \le 2n$$$) — the number of operations Moon will perform.

The second line should contain $$$q$$$ integers — the length of the prefix for each operation Moon performs, in order. After these operations, the permutation should be sorted.

If there are multiple valid solutions, you may print any of them.

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

L. Hello Hello zi and her caffeine problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

zi is feeling incredibly sleepy during a late-night coding round. To stay awake, she has lined up $$$n$$$ cups of coffee on her desk. The $$$i$$$-th cup has a specific caffeine level represented by an integer $$$a_i$$$.

She knows her limits: to fully wake up and solve problems, she must drink exactly three cups of coffee that have the exact same caffeine level.

Given the caffeine levels of all $$$n$$$ cups, help zi find a caffeine level that appears at least three times so she can wake up. If no such caffeine level exists, print $$$-1$$$ so she knows it's time to give up and just go to sleep.

Input

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

The first line of each test case contains contains an integer $$$n$$$ ($$$1 \le n \le 2*10^5$$$) — the total number of coffee cups on the desk.

Second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the caffeine levels of each coffee cup.

Output

For each test case, print any caffeine level that appears at least three times. If there is no such value, print $$$-1$$$.

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

M. Hello Hello fair game ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Batata and Moon have just discovered a massive treasure chest containing exactly $$$n$$$ ($$$n \ge 1$$$) golden coins. Unable to agree on who gets to keep the treasure, they decide to settle the dispute the only logical way: by playing a game.

The game is played with a single pile of $$$n$$$ coins. Batata and Moon take turns making moves, and Batata always goes first.

The rules for a single turn are as follows:

  • A player can choose a non-negative integer $$$k$$$ ($$$k \ge 0$$$) and remove exactly $$$2^k$$$ coins from the pile.
  • The player can repeat this action as many times as they want during their turn, as long as there are enough coins remaining.
  • Once the player is satisfied, they end their turn and let their friend play.

The player who is unable to make a valid move (because there are 0 coins left in the pile at the start of their turn) loses the game.

Assuming both Batata and Moon play optimally, determine who will win the game.

Input

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

Each test case consists of a single line containing one integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — the initial number of coins in the pile.

Output

For each test case, output the name of the winner on a new line: print "Batata" if Batata wins, or "Moon" if Moon wins.

Example
Input
2
4
16
Output
Batata
Batata
Note

In the first test case, there are $$$4$$$ coins. Batata can choose $$$k=2$$$ and remove exactly $$$2^2 = 4$$$ coins in a single action. The pile is now empty, so Moon cannot make a move. Batata wins.

In the second test case, there are $$$16$$$ coins. Batata can choose $$$k=4$$$ and remove exactly $$$2^4 = 16$$$ coins. Moon is left with $$$0$$$ coins and loses. Batata wins.