PSUT Programming Contest 2026
A. Osama hates the Corridor of Bits (Red)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Osama walks into a room filled with a row of glowing numbers, each one a reflection of his thoughts and memories.

The array is of length $$$n$$$, and the numbers are $$$a_1, a_2, \dots, a_n$$$, each shining with its own intensity.

He notices that each number shines with only a few glowing bits. Moreover, some pairs of numbers resonate with each other in a special way.

A pair of indices $$$(i, j)$$$ with $$$i \lt j$$$ is called beautiful if the bitwise OR of $$$a_i$$$ and $$$a_j$$$ is strictly greater than their bitwise XOR $$$\oplus$$$.

Formally, a pair $$$(i, j)$$$ is beautiful if:

$$$$$$ a_i \,|\, a_j \gt a_i \,XOR\, a_j $$$$$$

Osama wonders how many of these beautiful pairs exist in the array, each one a small moment of harmony amidst the glow.

Your task is to count all such beautiful pairs in the array.

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the length of the array.

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

Osama guarantees that the number of set bits (ones) in the binary representation of each number $$$a_i$$$ does not exceed $$$5$$$.

Output

Print a single integer — denotes the number of beautiful pairs asked.

Examples
Input
3
3 5 6
Output
3
Input
5
7 7 7 7 7
Output
10
Note

In the first example:

Pair ($$$1, 2$$$): $$$3 | 5 = 7$$$, $$$3 \oplus 5 = 6$$$. Since $$$7 \gt 6$$$, this is beautiful.

Pair ($$$1, 3$$$): $$$3 | 6 = 7$$$, $$$3 \oplus 6 = 5$$$. Since $$$7 \gt 5$$$, this is beautiful.

Pair ($$$2, 3$$$): $$$5 | 6 = 7$$$, $$$5 \oplus 6 = 3$$$. Since $$$7 \gt 3$$$, this is beautiful.

All $$$3$$$ pairs are beautiful.

B. Jebreel hates Moon's Game (Fushi)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Jebreel and Moon are playing a game on a graph with $$$n$$$ nodes and $$$m$$$ edges.

The Rules of the Game:

  1. Jebreel goes first. He chooses any uncolored node and colors it grey.;
  2. Moon then chooses a different uncolored node and colors it black.

They take turns until $$$5$$$ nodes total have been colored.

Jebreel wins if he manages to color a path of length $$$2$$$, meaning $$$3$$$ connected grey nodes. Otherwise, Moon wins.

Assuming both players play optimally, how many different starting nodes exist that guarantee a win for Jebreel?

Input

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

The first line of each test case contain two integers $$$n$$$ $$$(3 \le n\le 10^5)$$$, and $$$m$$$ $$$(0\le m\le \min\left(\frac{n(n-1)}{2},2\cdot 10^5\right)$$$ — denotes the number of nodes and edges in the graph respectively.

Then $$$m$$$ lines follow, the $$$i_{th}$$$ line contains two integers $$$u_i$$$ and $$$v_i$$$ $$$(1 \le u_i , v_i \le n)$$$ — denotes the two nodes that the $$$i_{th}$$$ edge connects.

It is guaranteed that there are no self-loops or multiple-edges in the given graph.

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

Output

For each test case, print how many different starting nodes exist that guarantee a win for Jebreel?

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

C. Jester hates binary strings (Blue)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Jester is given a binary string $$$s$$$ of length $$$n$$$, and an integer $$$k$$$ $$$(k \le n)$$$ representing the number of operations he must perform.

He must perform exactly $$$k$$$ operations.

In each operation, he deletes one character from the string:

  • Delete the leftmost character ($$$L$$$);
  • Delete the rightmost character ($$$R$$$).

The sequence of operations can be represented as a string of length $$$k$$$ consisting only of the characters $$$L$$$ and $$$R$$$.

After performing all $$$k$$$ operations, a result string $$$t$$$ is produced of length $$$n - k$$$

Jester's task is to count how many different operation strings of length $$$k$$$ result in a final string $$$t$$$ that contains $$$"01"$$$ as a substring.

Since the answer may be large, find it modulo $$$10^9+7$$$.

Input

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

The first line of each test case contains a two integer $$$n, k (1 \le k \le n \le 2 \cdot 10^5)$$$ — denotes the length of the string and the number of operation you must perform respectively.

The second line of each test case contains a string $$$s$$$ $$$(1 \le |s| \le n)$$$ — denotes the string and it is guaranteed that the string is binary.

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 the count how many different operation strings of length $$$k$$$ result in a final string $$$t$$$ that contains $$$"01"$$$ as a substring. The answer should be output modulo $$$10^9+7$$$

Example
Input
3
4 1
0101
5 1
01111
4 3
0011
Output
2
1
0

D. Asem Hates Valentine (Yellow)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Being single is not an option anymore – it is the destiny I am facing. In two days, it is Valentine's Day. Everyone is thinking about gifts for their partners… and here I am writing this problem.

I will show that I am not sad. I am happy. I am good. I am glad to be single. Why would I need commitments?

Anyway…

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

You may perform the following operation at most once:

Choose two indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i \ne j$$$), and swap $$$a_i$$$ and $$$a_j$$$.

Your task is to determine the maximum possible sum of the array after performing at most one such operation.

Input

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

For each test case:

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$) — we forgot the case when $$$n = 1$$$.

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

Output

For each test case, print a single integer – the maximum possible sum of the array after performing at most one swap.

Example
Input
1
3
4 1 2
Output
7

E. Moon hates Kilani's Stacks (Grey)
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Kilani gave Moon his least favorite data structure: a stack with a maximum capacity of $$$L$$$. Moon can perform the following two operations:

  • Push $$$x$$$: add an element with value $$$x$$$ to the top of the stack. If the stack already contains $$$L$$$ elements, the operation does nothing.
  • Pop: remove the element at the top of the stack. If the stack is empty, the operation does nothing.

You are given a sequence of $$$n$$$ operations, each of which is either type $$$1$$$ (Push) or type $$$2$$$ (Pop).

Then, you are given $$$q$$$ queries. In each query, you are given three integers $$$l$$$, $$$i$$$, and $$$k$$$.

For each query, consider a stack with capacity $$$l$$$, and apply only the first $$$i$$$ operations from the given sequence. After performing these operations, determine the value of the $$$k$$$th element in the stack (counted from the bottom, i.e., the bottom element is the first element).

If $$$k$$$ is greater than the current number of elements in the stack, print $$$-1$$$.

Input

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

For each test case:

  • The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — the number of operations and the number of queries.
  • The next $$$n$$$ lines describe the operations. Each line is one of the following:
    • push $$$x$$$ — push an integer $$$x$$$ onto the stack ($$$1 \le x \le 10^9$$$).
    • pop — remove the top element of the stack.
  • The next $$$q$$$ lines describe the queries. Each line contains three integers $$$l$$$, $$$i$$$, and $$$k$$$ ($$$1 \le l, i, k \le n$$$).

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

Output

For each test case, output $$$q$$$ lines.

For each query, print a single integer — the value of the $$$k$$$th element in the stack after applying the first $$$i$$$ operations on a stack with capacity limit $$$l$$$.

If the stack contains fewer than $$$k$$$ elements after these operations, print $$$-1$$$.

Example
Input
1
5 2
push 5
push 2
pop
push 4
pop
1 5 1
2 5 1
Output
-1
5

F. Aziz hate circles (Black)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Aziz is standing on the perimeter of a large circular park with a total circumference of $$$c$$$. There are $$$n$$$ specific points of interest on this circle that Aziz must visit.

The position of the $$$i$$$-th point is given by its clockwise distance $$$d_i$$$ from a fixed reference point $$$(0 \le d_i \lt c)$$$.

Aziz starts his journey at Point $$$1$$$.

He must visit every other point exactly once and finally return to Point $$$1$$$.

When moving between any two points $$$i$$$ and $$$j$$$, Aziz is smart and always takes the shortest path along the perimeter. The cost to travel between point $$$i$$$ and point $$$j$$$ is defined as

$$$cost(i, j) = \min(|d_i - d_j|, c - |d_i - d_j|)$$$

Find the minimum total distance Aziz must travel to complete his trip.

Input

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

For each test case:

The first line contains two integers $$$n$$$ and $$$c$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le c \le 10^9$$$) — denotes the number of points and the circumference of the circle respectively.

The second line contains $$$n$$$ integers $$$d_1, d_2, \dots, d_n$$$ ($$$0 \le d_i \lt c$$$) — denotes the positions of the points.

It is guaranteed that all $$$d_i$$$ are distinct and $$$d_1$$$ is the starting point.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 minimum total distance to visit all points and return to the start.

Example
Input
2
3 100
0 10 20
3 10
0 3 7
Output
40
10

G. Asem hates getting averaged (White)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output), and in Python — sys.stdout.flush().

In this problem, the jury has a hidden permutation $$$p$$$ of length $$$n$$$. The permutation contains all integers from $$$1$$$ to $$$n$$$ exactly once. The value of $$$n$$$ is given to you at the beginning.

You can make queries to the testing system. Each query consists of two different indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i \ne j$$$). After printing a query, you must flush the output stream.

For each query "? i j", the testing system responds with a single integer equal to $$$\lfloor \frac{p_i + p_j}{2} \rfloor$$$ where $$$p_i$$$ and $$$p_j$$$ are the values of the hidden permutation at positions $$$i$$$ and $$$j$$$.

When your program determines the entire permutation, print the string !$$$p_1\ p_2\ \dots\ p_n$$$, where $$$p_1, p_2, \dots, p_n$$$ is the reconstructed permutation, and terminate your program normally immediately after flushing the output stream.

Your program is allowed to make no more than $$$1.9n$$$ queries (not including printing the final answer) to the testing system.

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.

The first line contains an integer $$$n$$$ ($$$5 \le n \le 10^5$$$) — the length of the hidden permutation.

Each following line contains the response to one of your queries. The $$$i$$$-th such line is the response to your $$$i$$$-th query and contains a single integer equal to $$$\lfloor \frac{p_i + p_j}{2} \rfloor$$$ where $$$(x_i, y_i)$$$ is the pair of indices printed in your $$$i$$$-th query.

The testing system will allow you to read the response to a query only after your program prints the query and performs the flush operation.

When your program prints the final answer using the format ! $$$p_1 p_2 \dots p_n$$$, it must terminate immediately.

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

Output

To make the queries, your program must use standard output.

Each query must be printed in the format "? i j", where $$$1 \le i, j \le n$$$ and $$$i \ne j$$$. Print exactly one query per line and perform the flush operation after each query.

The response to the query will be provided on standard input after you flush the output.

When your program has reconstructed the permutation, print the final answer in the format ! $$$p_1 p_2 \dots p_n$$$, where $$$p_1, p_2, \dots, p_n$$$ is the permutation, flush the output, and terminate your program.

Example
Input
1
5

3

3

2

1
Output
? 1 5

? 2 3

? 2 5

? 4 5

! 5 4 3 2 1
Note

In the sample test case, suppose the hidden permutation is $$$p = [5, 4, 3, 2, 1]$$$.

Each query ? i j returns $$$\lfloor \frac{p_i + p_j}{2} \rfloor$$$.

Now let us verify the sample interaction.

For the query ? 1 5, $$$\lfloor \frac{5 + 1}{2} \rfloor = \lfloor \frac{6}{2} \rfloor = 3$$$.

For the query ? 2 3, $$$\lfloor \frac{4 + 3}{2} \rfloor = \lfloor \frac{7}{2} \rfloor = 3$$$.

For the query ? 2 5, $$$\lfloor \frac{4 + 1}{2} \rfloor = \lfloor \frac{5}{2} \rfloor = 2$$$.

For the query ? 4 5, $$$\lfloor \frac{2 + 1}{2} \rfloor = \lfloor \frac{3}{2} \rfloor = 1$$$.

Thus, all responses are consistent with the permutation ! 5 4 3 2 1.

H. Shoree hates Moon's EX (Mint)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Shoree is Moon's friend, she loves math, especially phi $$$\varphi$$$, the euler totient function, Shoree decided to make her own function called the Shoree function, defined as

$$$shoree(x) = \varphi(x)$$$ $$$XOR$$$ $$$x$$$

Given $$$l$$$ and $$$r$$$, find

$$$\operatorname{MEX}$$$($$$shoree(l), shoree(l+1), ..., shoree(r)$$$)
Input

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

The first line and only of each test case contain two integers $$$l, r$$$ $$$(1 \le l \le r \le 10^9)$$$ — denotes the number of queries and the left boundary and the right boundary of the sum of the function respectively.

Output

for each test case, print $$$\operatorname{MEX}$$$($$$shoree(l), shoree(l+1), ..., shoree(r)$$$)

Example
Input
3
2 3
1 1
1 7
Output
0
1
2
Note

$$$\varphi(x)$$$ is defined as Euler's totient function counts the positive integers up to a given integer $$$n$$$ that are relatively prime to $$$n$$$,

Note that $$$\varphi(1)$$$ $$$=$$$ $$$1$$$

For example $$$\varphi(9) = 6$$$ because the six numbers $$$1$$$, $$$2$$$, $$$4$$$, $$$5$$$, $$$7$$$ and $$$8$$$ are all the numbers that are from $$$1$$$ to $$$9$$$ and are relatively prime to $$$9$$$

The $$$\operatorname{MEX}$$$ (Minimum EXcluded value) of an array is the smallest non-negative integer that is not in the array. For example:

  • The $$$\operatorname{MEX}$$$ of $$$[1, 2, 3]$$$ is $$$0$$$
  • The $$$\operatorname{MEX}$$$ of $$$[0, 1, 2]$$$ is $$$3$$$
  • The $$$\operatorname{MEX}$$$ of $$$[0, 1, 3]$$$ is $$$2$$$

I. Rayo hates unique substrings (Neon)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Rayo loves strings, but he dislikes unique substrings. Kilani decided to give him a challenge involving both.

You are given a string $$$s$$$ of length $$$n$$$ and an integer $$$m$$$.

Construct a new string $$$t$$$ of length $$$m$$$ as follows:

For each index $$$i$$$ ($$$1 \le i \le m$$$):

$$$$$$ t[i] = \begin{cases} s[i], & \text{if } i \le n, \\ s[i - n], & \text{otherwise}. \end{cases} $$$$$$

In other words, after copying the first $$$n$$$ characters from $$$s$$$, the string continues by repeating the same pattern every $$$n$$$ characters.

Your task is to determine the number of distinct (unique) substrings of the string $$$t$$$.

Input

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

For each test case:

  • The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$n \le m \le 10^9)$$$ — the length of the string $$$s$$$ and the required length of $$$t$$$.
  • The second line contains a string $$$s$$$ of length $$$n$$$ that contains lowercase English letters.

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

Output

For each test case, print a single integer — the number of distinct substrings of the constructed string $$$t$$$.

Example
Input
2
2 3
ah
3 5
aaa
Output
5
5
Note

In the first sample case, the constructed string is aha.

It has 5 distinct sub strings which are: [a, ah, aha, ha, h].

In the second sample case, the constructed string is aaaaa.

It has 5 distinct sub strings which are: [a, aa, aaa, aaaa, aaaaa].

J. Asem hates Coprimes (Green)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Asem recently learned about coprime numbers and immediately started hating them.

Given an integer $$$N$$$, Asem wants to find the largest integer $$$M$$$ such that $$$1 \le M \lt N$$$ and $$$M$$$ is NOT coprime with $$$N$$$.

Two integers are said to be coprime if their greatest common divisor is equal to $$$1$$$.

Help Asem find the answer.

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 a single integer $$$N$$$ $$$(2 \le N \le 10^6)$$$.

Output

For each test case, print a single integer – the maximum integer $$$M$$$ such that $$$1 \le M \lt N$$$ and $$$\gcd(M, N) \gt 1$$$.

If no such integer exists, print $$$-1$$$.

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

K. Kilani & Ayoub hate (Gold)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ayoub gave Kilani an array $$$a$$$ of length $$$n$$$, where each element satisfies $$$1 \le a_i \le n$$$. The elements of $$$a$$$ are not necessarily distinct.

He may reorder (permute) the elements of the array in any way he wants. After choosing an ordering, he constructs an undirected graph with $$$n$$$ vertices labeled $$$1$$$ to $$$n$$$, and for each index $$$i$$$, he adds an edge between vertex $$$i$$$ and vertex $$$a_i$$$.

Self-loops (when $$$i = a_i$$$) and multiple edges are allowed.

Determine whether there exists a reordering of the array such that the resulting graph is connected.

Input

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

For each test case:

  • The first line contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the length of the array.
  • The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

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

Output

For each test case:

  • If it is impossible to reorder the array so that the resulting graph is connected, print NO.
  • Otherwise, print YES on the first line, and on the second line print $$$n$$$ integers — a reordering of the array $$$a_1, a_2, \dots, a_n$$$ such that if we add an undirected edge between $$$i$$$ and $$$a_i$$$ for every $$$i$$$, the resulting graph is connected.
Example
Input
4
1
1
2
1 2
4
4 4 4 4
5
1 2 3 4 5
Output
Yes
1 
Yes
2 1 
Yes
4 4 4 4 
Yes
2 3 4 5 1

L. Moon hates Rayo's RGB (Orange)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Rayo gave Moon a string that only has the letters $$$R$$$, $$$G$$$, $$$B$$$ in it.

You can replace any two adjacent, differing characters with the character that is not present in that pair, for example you can replace RG with B, but you can't replace RR.

Determine if the string can be reduced to the single character $$$G$$$

Input

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

The first line of each test case contains a single string $$$s$$$ $$$(1 \le |s| \le 10^6)$$$ that only contains $$$R$$$, $$$G$$$, and $$$B$$$ — denotes the string.

It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output "YES" (without quotes) if $$$s$$$ if can be reduced to the single character $$$G$$$ , and "NO" (without quotes) otherwise.

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

Examples
Input
4
RB
RGB
RRGB
RRG
Output
YES
NO
NO
YES
Input
1
RRRRRRRRRG
Output
NO

M. Asem hates Moon's EX (Pink)
time limit per test
2 s.
memory limit per test
256 MB
input
standard input
output
standard output

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

You must choose exactly one integer $$$X (0 \le X \le 10^9)$$$ and apply the following operation once: replace every element $$$a_i$$$ with $$$a_i$$$ $$$\oplus$$$ $$$X$$$ (the character $$$\oplus$$$ denotes bitwise $$$XOR$$$).

After performing this operation, let the resulting array be $$$b$$$. Your task is to determine the maximum possible $$$MEX$$$ of the array $$$b$$$.

The $$$\operatorname{MEX}$$$ (Minimum EXcluded value) of an array is the smallest non-negative integer that is not in the array. For example:

  • The $$$\operatorname{MEX}$$$ of $$$[1, 2, 3]$$$ is $$$0$$$
  • The $$$\operatorname{MEX}$$$ of $$$[0, 1, 2]$$$ is $$$3$$$
  • The $$$\operatorname{MEX}$$$ of $$$[0, 1, 3]$$$ is $$$2$$$
Input

The first line contains an integer $$$t (1 \le t \le 10^4)$$$ — denotes 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)$$$ — denotes the length of the array.

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

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 maximum $$$MEX$$$ that can be obtained after applying the operation exactly once.

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