ICPC India Online Prelims (2025 - 2026)
A. How many?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A college club is going to host an ICPC styled contest for its college students. Each team should have exactly three participants. There will be $$$n$$$ teams. How many participants will there be in total?

Input

The only line of input contains an integer $$$n$$$ ($$$1 \le n \le 1000$$$) — denoting the number of teams that will be participating.

Output

Output the total number of participants.

Example
Input
1
Output
3

B. Pseudo Palindrome
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$$$ and a non-negative integer $$$d$$$.

Is it possible to rearrange $$$a$$$ in such a way that $$$|a_i - a_{n + 1 - i}| \le d$$$ for all $$$i$$$ ($$$1 \le i \le n$$$)?

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

The first line of each test case contains integers $$$n$$$ and $$$d$$$ ($$$1 \le n \le 2000$$$, $$$0 \le d \le 10^9$$$) — the length of $$$a$$$ and the integer $$$d$$$.

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

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

Output

For each test case, output "YES" if it is possible to rearrange $$$a$$$. Otherwise, output "NO". You can output "YES" and "NO" in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive response).

Example
Input
3
1 1
1
2 0
1 2
2 1000
1 2
Output
YES
NO
YES
Note

In the first test case, the given array is already valid.

In the second test case, it can be proven that there is no valid rearrangement of $$$a$$$.

In the third test case, the valid rearrangements are $$$[1, 2]$$$ and $$$[2, 1]$$$.

C. XOR LCM
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a positive integer $$$c(1 \le c \le 10^7)$$$.

You need to find two positive integers $$$a$$$ and $$$b$$$ such that:

  • $$$1 \le a, b \le 10^{17}$$$
  • $$$ (a \oplus c) + (b \oplus c) = lcm(a, c) + lcm(b, c)$$$, where $$$\oplus$$$ is the bitwise XOR operator and $$$lcm(x, y)$$$ is the lowest common multiple of $$$x$$$ and $$$y$$$.

It can be proven that it is always possible to find $$$a$$$ and $$$b$$$ for the given constraints.

Input

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains an integer $$$c$$$ ($$$1 \le c \le 10^7$$$).

Output

For each test case, output two integers $$$a$$$ and $$$b$$$.

Example
Input
3
1
2
7
Output
88 71
80 62
1 35

D. Make Empty
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation $$$p$$$ of $$$[1, 2, \ldots n]$$$ ($$$n$$$ is even).

You can perform the following operation:

  • Select a subsequence $$$^\dagger$$$ (say $$$t$$$) of length $$$2k$$$ ($$$k$$$ does not need to be the same across operations) such that $$$\max(t_1, t_2, \ldots, t_k) \lt \min(t_{k+1}, t_{k+2}, \ldots, t_{2k})$$$ or $$$\min(t_1, t_2, \ldots, t_k) \gt \max(t_{k+1}, t_{k+2}, \ldots, t_{2k})$$$. Remove $$$t$$$ from $$$p$$$.

You want to make $$$p$$$ empty using the minimum number of operations.

You must also print the subsequence used in each operation, printing the values (not the indices).

$$$^\dagger$$$ A sequence $$$x$$$ is a subsequence of a sequence $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by deleting several (possibly, zero or all) elements. For example, $$$[1, 3]$$$, $$$[1, 2, 3]$$$, and $$$[2, 3]$$$ are subsequences of $$$[1, 2, 3]$$$. On the other hand, $$$[3, 1]$$$ and $$$[2, 1, 3]$$$ are not subsequences of $$$[1, 2, 3]$$$.

Input

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

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$n$$$ is even) — the length of $$$p$$$.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \le n$$$) — the elements of the permutation $$$p$$$.

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 number of operations, $$$x$$$, on the first line. Then print $$$x$$$ lines. On each line, output the length of the subsequence followed by the elements of a valid subsequence. Note that you must print the values, not the indices.

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

In the first test case, we can select $$$t = p$$$ and make $$$p$$$ empty in one operation.

In the second test case, we can again select $$$t = p$$$ in the first operation. We can see that $$$t$$$ is valid because $$$\max(t_1, t_2) = 2$$$ and $$$\min(t_3, t_4) = 3$$$, and $$$2 \lt 3$$$.

In the third test case, it is not possible to make $$$p$$$ empty in one operation because $$$\max(p_1, p_2) \gt \min(p_3, p_4)$$$ and $$$\min(p_1,p_2) \lt \max(p_3,p_4)$$$. In the first operation, we can select $$$t = [2, 4]$$$. On removing $$$t$$$ from $$$p$$$, we get $$$p = [3, 1]$$$. So, we can select $$$t = p$$$ in the second operation.

E. Counting Is Fun
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes and a positive integer $$$c$$$. The $$$i$$$-th edge connects the nodes $$$u_i$$$ and $$$v_i$$$.

Before the traversal begins, choose a permutation $$$p$$$ of $$$[1, 2, \ldots, n - 1]$$$ and label the $$$i$$$-th edge with $$$p_i$$$. These labels remain fixed throughout the traversal.

You start from node $$$1$$$ with an integer $$$x = 1$$$.

During the traversal, you may repeatedly perform one of the following operations:

  • Operation A: Traverse an edge adjacent to your current node if it is not labelled with $$$x$$$. After traversing, you move to the node on the other end of that edge.
  • Operation B: Increment $$$x$$$ by $$$1$$$.

You must start at node $$$1$$$, visit all nodes, and return to node $$$1$$$. The cost of a traversal is the number of times you perform Operation B.

Define $$$f(p)$$$ as the minimum cost of a traversal when the edges are labelled according to the permutation $$$p$$$.

Your task is to count the number of permutations $$$p$$$ of $$$[1, 2, \ldots n - 1]$$$ such that $$$f(p) = c$$$. Since the number might be large, output it modulo $$$998\,244\,353$$$.

Input

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

The first line of each test case contains integers $$$n$$$ and $$$c$$$ ($$$2 \le n \leq 2 \cdot 10^5$$$, $$$1 \le c \le n - 1$$$) — the number of vertices and the target cost.

The next $$$n-1$$$ lines describe the edges of the tree. The $$$i$$$-th of these lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i \lt v_i \le n$$$) — the endpoints of the $$$i$$$-th edge.

The edges are numbered in the order they are given in the input. You will later label the $$$i$$$-th edge with $$$p_i$$$, where $$$p$$$ is a permutation of $$$[1, 2, \ldots, n - 1]$$$.

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

Output

For each test, find the number of valid permutations modulo $$$998\,244\,353$$$.

Example
Input
3
2 1
1 2
5 1
1 2
1 3
1 4
1 5
5 3
1 2
1 3
1 4
1 5
Output
1
24
0
Note

In the second test case, all $$$(n-1)!$$$ permutations are valid.

In the third test case, it can be proven that no permutation is valid.

F. Non Unique
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$. Let $$$f(a, i)$$$ denote the number of indices $$$j$$$ such that $$$1 \le j \lt i$$$ and $$$a_j \gt a_i$$$. Let $$$F(a)$$$ be the set of indices $$$i$$$ having the maximum value of $$$f(a, i)$$$.

You do not want $$$F(a)$$$ to consist of only one element, so you may perform the following operation any number of times:

  • Select $$$1 \le i \lt n$$$, and swap $$$a_i$$$ and $$$a_{i + 1}$$$.

Let $$$x$$$ be the minimum number of operations needed so that $$$|F(a)| \ge 2$$$. It can be proven that $$$x$$$ is finite.

Find the number of ways to achieve $$$|F(a)| \ge 2$$$ in exactly $$$x$$$ operations.

Since the number might be large, output it modulo $$$998\,244\,353$$$.

Two ways are different if there exists an index $$$j$$$ such that the indices selected in the $$$j$$$-th operation are different.

Input

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

The first line of each test case contains a positive integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the length of the array $$$a$$$.

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

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

Output

For each test case, print the number of ways modulo $$$998\,244\,353$$$.

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

In the first test case, we do not need to perform any operation. So, the number of ways is $$$1$$$.

In the second test case, we can get $$$|F(a)| \ge 2$$$ by performing $$$1$$$ operation. There are $$$2$$$ ways: we can select $$$i = 1$$$ or $$$i = 2$$$.

In the third test case, we can achieve $$$|F(a)| \ge 2$$$ by performing $$$2$$$ operations. There are $$$2$$$ ways:

  • Select $$$i = 1$$$ in the first operation and $$$i = 2$$$ in the second operation. Then we get $$$a = [3, 1, 2]$$$ and $$$F(a) = [2, 3]$$$.
  • Select $$$i = 2$$$ in the first operation and $$$i = 1$$$ in the second operation. Then we get $$$a = [1, 2, 3]$$$ and $$$F(a) = [1, 2, 3]$$$.