The 2025 Damascus University Collegiate Programming Contest
A. Tree Labeling
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a tree$$$^{[6]}$$$ of $$$n$$$ vertices, find the lexicographically$$$^{[2]}$$$ smallest string $$$s$$$ that satisfies the following:

  • String $$$s$$$ only consists of letters 'a', 'b', and 'c'.
  • For every edge $$$(u,v)$$$ of the tree, $$$s_u \neq s_v$$$.
Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — denoting the number of vertices in the tree.

Each of the following $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — denoting the indices of the vertices connected by an edge.

It is guaranteed that the given edges form a tree.

Output

Output a single line, containing a string of length $$$n$$$ — the lexicographically smallest achievable string.

Examples
Input
3
1 2
1 3
Output
abb
Input
4
1 3
3 4
4 2
Output
aabc

B. Free Problems
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The judges of DCPC are offering free problems to the contestants; you just have to take them!

They will ask you if you want a free problem.

If you want one, you should output "Yee", and the judges will give you a free problem. Anything else, even "Yes" or "Sure", and they won't give you one.

So, do you want a free problem?

Input

The first line contains a single sentence "Do you want a free problem?".

Output

Print "Yee" (without quotes) if you want a free problem.

You can output the answer in any case (upper or lower). For example, the strings "yEe", "yee", "YEE", and "YeE" will be recognized as positive responses.

Example
Input
Do you want a free problem?
Output
yee

C. GCD on Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a tree$$$^{[6]}$$$ with $$$n$$$ vertices, where the $$$i$$$-th vertex is labeled with a positive integer $$$a_i$$$. A tree is eggy when the greatest common divisor of all its vertex-values is equal to $$$1$$$.

You have to process $$$q$$$ queries as follows:

  • $$$i\; x$$$: update the value of $$$i_{th}$$$ vertex by assigning $$$a_i = x$$$.
  • After each update, check if there's any edge in the tree that, when removed, splits the tree into two trees, where at least one of those trees is eggy.
Input

The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — denoting the number of vertices in the tree.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) — representing the values of the vertices.

Each of the following $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — denoting the indices of the vertices connected by an edge.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — representing the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$i$$$ and $$$x$$$ ($$$1 \le i \le n, 1 \le x \le 10^{18}$$$).

It is guaranteed that the given edges form a tree.

Output

After each query, print "YES" (without quotes) if there's any valid edge in the tree, and "NO" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Examples
Input
2
2 2
1 2
4
1 3
2 1
1 2
2 2
Output
No
Yes
Yes
No
Input
3
6 2 3
1 2
1 3
5
2 6
1 2
1 3
3 5
3 6
Output
No
Yes
No
Yes
No

D. Ascendio or Descendio
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integers $$$n$$$ and $$$m$$$. Find the number of ways to fill an $$$n\times m$$$ grid with the numbers $$$1, 2, \ldots, n \times m$$$, using each number exactly once, such that the following conditions are satisfied:

  • Every row forms a strictly monotonic$$$^{[5]}$$$ sequence.
  • Every column forms a strictly monotonic sequence.

Count the number of valid fillings, modulo $$$998\,244\,353$$$.

Input

The only line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2025$$$).

Output

Output a single integer — the number of valid fillings, modulo $$$998\,244\,353$$$.

Examples
Input
1 1
Output
1
Input
2 1
Output
2
Input
2 2
Output
24
Input
3 2
Output
80
Input
2024 2025
Output
831665454
E. Permutation Game
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a permutation$$$^{[3]}$$$ $$$p$$$ of length $$$n$$$. Obada and the Harraaak are playing a game with this permutation with an initial score of $$$0$$$.

The players must follow a set of rules described as follows:

  • On each turn, a player must choose an integer $$$x$$$ from the permutation that has not been selected before. The player either adds or subtracts $$$x$$$ from the score.
  • During the first turn, a player can select any integer.
  • For all turns except the first, if $$$m$$$ is the integer selected in the previous turn and $$$p_m$$$ is not chosen yet, then the player must select $$$p_m$$$ in this turn. Otherwise, they can pick any integer that has not been selected yet.
  • The game terminates when all integers in the permutation have been selected.

The players alternate turns, with Obada starting first. Obada aims to maximize the score of the game, while the Harraaak aims to minimize it.

Your task is to find the final score of the game when both players play optimally.

Input

The first line of the input 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^6$$$) — the length of the permutation.

The second line of each test case consists of $$$n$$$ space-separated integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$).

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

Output

Output $$$t$$$ lines, the $$$i$$$-th of which contains a single integer — the final score of the game for the $$$i$$$-th test case when both players play optimally.

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

F. Coin Flip
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem. Your program will interact with the judge using standard input and output.

You are given an array $$$a$$$ of $$$n$$$ positive integers and an integer $$$k$$$, where $$$2k \leq n$$$. You have an initial score equal to $$$0$$$.

You will be asked $$$k$$$ queries. For each query, you will be given an integer $$$x \in \{1, 2\}$$$. You must choose an index $$$i$$$ ($$$1 \leq i \leq n$$$) such that$$$^\dagger$$$:

  • $$$i$$$ is divisible by $$$x$$$;
  • The index $$$i$$$ has not been chosen in any previous query;

Whenever you choose some index $$$i$$$ in some query, the value of $$$a_i$$$ is added to the score.

Your task is to maximize the score after completing all $$$k$$$ queries.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le 2k \le n \le 10^5$$$).

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

Interaction

The interaction proceeds as follows for $$$k$$$ times:

  • The judge will output a single integer $$$x \in \{1, 2\}$$$.
  • You must respond with a single integer $$$i$$$ ($$$1 \leq i \leq n$$$) that satisfies the conditions above$$$^\dagger$$$.
  • The judge will output "1" if $$$i$$$ is divisible by $$$x$$$ and it has not been chosen before in any previous query, and "0" otherwise.

If your program makes an invalid response, then the judge's response will be "0". After receiving such a response, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, it may receive any other verdict.

After responding to a query, do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • sys.stdout.flush() in Python;
  • std::io::stdout().flush() in Rust;
  • see the documentation for other languages.
Example
Input
6 3
5 1 3 4 2 6
1
1
1
1
2
1
Output
1
6
4
Note

Sample explanation:

The size of the array is 6 and there are 3 queries. The first 2 lines describe the array and the number of queries.

In the first query, we must choose an index divisible by $$$1$$$, we choose the index $$$1$$$ and since it's divisible by $$$1$$$ and has not been chosen before, the judge will print $$$1$$$ to confirm that the chosen index is valid.

In the second query, we must choose an index divisible by $$$1$$$, we choose the index $$$6$$$ and since it's divisible by $$$1$$$ and has not been chosen before, the judge will print $$$1$$$ to confirm that the chosen index is valid. Note that if we chose $$$1$$$ instead the judge will print $$$0$$$ (since it has been chosen before).

In the third query, we must choose an index divisible by $$$2$$$, we choose the index $$$4$$$ and since it's divisible by $$$2$$$ and has not been chosen before, the judge will print $$$1$$$ to confirm that the chosen index is valid. Note that if we chose $$$6$$$ instead the judge will print $$$0$$$ (since it has been chosen before), and if we chose $$$3$$$ the judge will also print $$$0$$$ (since it's not divisible by $$$2$$$).

Note that over all combinations of: two indices divisible by 1 and one index divisible by 2, the maximum possible result is 15 (which is equal to the result in the example) and all chosen indices are distinct and satisfy the divisibility condition, so the result is considered correct.

G. Pretty Prime Collection
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a deck of $$$n$$$ cards, each labeled with a number $$$a_i$$$. The game begins with an empty hand and an initial total score of zero.

On the $$$i$$$-th turn, you must pick up the $$$i$$$-th card with value $$$a_i$$$, then optionally discard some cards from your hand, ensuring that after this step, the bitwise XOR$$$^{[8]}$$$ of any two remaining cards in hand is a prime number$$$^{[11]}$$$. The score for this turn is the sum of the values of all cards in your hand, which is then added to the total score.

Determine the maximum possible total score after completing all $$$n$$$ turns.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 50$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 150$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \lt 2^{20}$$$).

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

Output

For each test case, output one line containing a single integer — the maximum score you can get.

Example
Input
3
5
1 2 3 4 5
9
9 9 8 2 4 4 3 5 3
2
323468 765165
Output
24 
103 
1412101
Note

Cards picked during their respective turns are underlined, while discarded cards are crossed out.

In the first test case, you can process the initial empty hand $$$\{\}$$$ and total score $$$0$$$ as follows:

  • after completing the first turn: $$$\{\underline{1}\}$$$ $$$\overset{\text{following removal}}{\xrightarrow{\hspace{1.3cm}}}$$$ $$$\{1\}$$$ and a total score of $$$0 + 1 = 1$$$;
  • after completing the second turn: $$$\{1, \underline{2}\}$$$ $$$\overset{\text{following removal}}{\xrightarrow{\hspace{1.3cm}}}$$$ $$$\{1, 2\}$$$ and a total score of $$$1 + 3 = 4$$$;
  • after completing the third turn: $$$\{1, \not{2}, \underline{3}\}$$$ $$$\overset{\text{following removal}}{\xrightarrow{\hspace{1.3cm}}}$$$ $$$\{1, 3\}$$$ and a total score of $$$4 + 4 = 8$$$. Note that cards with values $$$2$$$ and $$$3$$$ cannot be held in hand simultaneously since $$$2 \oplus 3 = 1$$$, which isn't a prime number. To resolve this, we can discard the card with value $$$2$$$;
  • after completing the fourth turn: $$$\{1, 3, \underline{4}\}$$$ $$$\overset{\text{following removal}}{\xrightarrow{\hspace{1.3cm}}}$$$ $$$\{1, 3, 4\}$$$ and a total score of $$$8 + 8 = 16$$$;
  • after completing the fifth turn: $$$\{1, 3, 4, \not{\underline{5}}\}$$$ $$$\overset{\text{following removal}}{\xrightarrow{\hspace{1.3cm}}}$$$ $$$\{1, 3, 4\}$$$ and a total score of $$$16 + 8 = 24$$$.

H. Mexican Subarrays
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$. Count the number of non-empty subarrays$$$^{[1]}$$$ ($$$a[l, l + 1, \ldots, r]$$$) such that its sum is equal to its MEX$$$^{[10]}$$$.

Input

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

The second line of the input consists of $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

Output

Output one line containing a single integer — the number of non-empty subarrays such that their sum is equal to their MEX.

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

I. MST Queries
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a connected, undirected, weighted graph with $$$n$$$ vertices and $$$m$$$ edges labeled from $$$1$$$ through $$$m$$$. Define:

  • $$$G[l, r]$$$: the graph on all $$$n$$$ vertices containing only the edges numbered from $$$l$$$ to $$$r$$$.
  • $$$\text{W}(H)$$$: the total weight of a minimum spanning tree$$$^{[7]}$$$ of graph $$$H$$$, or $$$\infty$$$ in case $$$H$$$ is disconnected.

You have to process $$$q$$$ queries. For each query specified by a range $$$[l, r]$$$, count the number of pairs $$$(x, y)$$$ that satisfy the following:

  • $$$l \leq x \leq y \leq r$$$;
  • $$$\text{W}(G[x, y]) = \text{W}(G[1, m])$$$.
Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$n-1 \leq m \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$) — denoting the number of vertices, the number of edges, and the number of queries.

The $$$i$$$-th of the next $$$m$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$1 \leq w_i \leq 10^9$$$) — representing the edges of the graph. It is guaranteed that the given edges form a connected graph. Note that the graph may contain self-loops and multiple edges.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le m$$$).

Output

For each query, output a single integer — the number of valid pairs $$$(x, y)$$$.

Example
Input
4 6 3
1 4 20
1 2 10
2 3 20
3 4 5
1 3 15
2 4 25
1 6
2 5
1 5
Output
4
1
2

J. AND Construction
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two integers $$$n$$$ and $$$k$$$. An array $$$a$$$ is considered good if the following conditions hold:

  • The length of $$$a$$$ is equal to $$$n$$$.
  • $$$a$$$ contains positive integers.
  • The sum of elements of $$$a$$$ is equal to $$$k$$$ (i.e. $$$\sum a_i = k$$$).

The cost of the array $$$a$$$ is equal to the sum of $$$a_i$$$ $$$\&$$$ $$$a_{i - 1}$$$ for all $$$i$$$ such that $$$1 \lt i \le n$$$, where $$$\&$$$ is the bitwise AND$$$^{[9]}$$$ operator.

Your task is to find the minimum cost of a good array.

Input

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

Each line of the following $$$t$$$ lines of the input consists of two space-separated integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^6, n \le k \le 10^9$$$).

Notice that there is no limit on the sum of $$$n$$$ over all the test cases.

Output

Output $$$t$$$ lines, the $$$i$$$-th of which contains a single integer — the minimum cost of a good array in the $$$i$$$-th testcase.

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

K. Derangements
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two integers $$$n$$$ and $$$k$$$, your task is to find the $$$k$$$-th smallest derangement$$$^{[4]}$$$ of length $$$n$$$ when all derangements of length $$$n$$$ are listed in lexicographical order$$$^{[2]}$$$.

Input

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

The first line of each testcase contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le 10^{15}$$$).

It is guaranteed that there are at least $$$k$$$ derangements of length $$$n$$$.

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

Output

For each test case, output a single line containing $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ — the $$$k$$$-th smallest derangement of length $$$n$$$.

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

In the fourth test case, below is the list of all derangements of length $$$4$$$ in lexicographical order:

$$$$$$[2, 1, 4, 3] , [2, 3, 4, 1] , [2, 4, 1, 3] , [3, 1, 4, 2] , [3, 4, 1, 2] , [3, 4, 2, 1] , [4, 1, 2, 3] , [4, 3, 1, 2] , [4, 3, 2, 1]$$$$$$

Thus, the $$$6$$$-th smallest derangement of length $$$4$$$ is $$$[3, 4, 2, 1]$$$.

L. Guess What: Another Permutation Game
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a permutation$$$^{[3]}$$$ $$$p$$$ of length $$$n$$$ and two integers $$$k_1$$$ and $$$k_2$$$, both not exceeding $$$n$$$. There is also an integer array $$$a$$$, initially empty. Obada and Osama are playing a game. Obada starts first, and the players alternate turns. On their turn, the player must do one of the following:

  • Remove the leftmost element from $$$p$$$ and append it to the end of the array $$$a$$$.
  • Append $$$0$$$ to the end of the array $$$a$$$.

There is one restriction, the player can't make a move that makes the array $$$a$$$ invalid.

The array $$$a$$$ is invalid when at least one of the following two conditions hold:

  • The array $$$a$$$ contains a subarray of length more than $$$k_1$$$ that contains no $$$0s$$$.
  • The array $$$a$$$ contains a subarray of length more than $$$k_2$$$ which elements are all $$$0s$$$.

The game ends when $$$p$$$ is empty, and the score of the game is equal to the largest number removed from the permutation by Obada in his turn.

Obada wants to maximize the score of the game, while Osama wants to minimize it. You are asked to find the score of the game if both players play optimally.

Input

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

The first line of each test case contains three space separated integers $$$n$$$, $$$k_1$$$ and $$$k_2$$$ ($$$1 \le n \le 10^6, 1 \le k_1, k_2 \le n$$$).

The second line of each test case contains $$$n$$$ space separated integers $$$p_1, p_2, ..., p_n$$$ ($$$1 \le p_i \le n$$$) — representing the permutation.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For each test case, print a single line containing the final score of the game.

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

M. Hayyan and Subarray Sums
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ of length $$$n$$$. A partition of the array $$$a$$$ is dividing it into subarrays$$$^{[1]}$$$ such that each element of $$$a$$$ belongs to exactly one subarray. Two partitions are considered different if there is a subarray that is present in one of the partitions but not in both of them.

We define the cost of a partition of $$$a$$$ as the following:

  1. Let's initialize cost to be equal to $$$0$$$.
  2. For each subarray of $$$a$$$ (i.e. $$$a[l, l + 1, \ldots, r]$$$) that is present in the partition, let $$$s$$$ be equal to the sum of integers in this subarray (i.e. $$$\displaystyle\sum_{i=l}^r a_i$$$).
  3. Update cost to be equal to cost $$$\oplus$$$ $$$s$$$, where $$$\oplus$$$ is the bitwise XOR$$$^{[8]}$$$ operator.

Find the bitwise XOR of the costs of all possible partitions of $$$a$$$.

Input

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

For each test case, the first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the array $$$a$$$.

The second line consists of $$$n$$$ spaces-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

Output $$$t$$$ lines, the $$$i$$$-th of which contains a single integer — the answer for the $$$i$$$-th test case.

Example
Input
3
1
1
2
1 2
3
1 2 3
Output
1
0
2

N. Colored Sticks
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ consisting of $$$n$$$ positive integers. For each $$$i$$$ such that $$$1 \le i \le n$$$, there are $$$a_i$$$ sticks of length $$$i$$$, and let $$$m$$$ be equal to the total number of sticks (i.e. $$$m = \displaystyle\sum_{i=1}^{n} a_i$$$).

You have $$$m$$$ colors, and for each stick, you must choose an integer $$$k$$$ such that $$$1 \le k \le m$$$, and color the $$$i$$$-th stick with the $$$k$$$-th color.

Your goal is to color these sticks in such a way that it would be impossible to form a square by choosing four sticks of the same color.

What is the minimum number of different colors you need to use?

Input

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

The second line of the input consists of $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the number of sticks of each length.

Output

Output one line containing a single integer — the minimum number of distinct colors that are required.

Example
Input
3
4 1 1
Output
2
Note

In the first test case:

The total number of sticks is $$$4 + 1 + 1 = 6$$$.

It's possible to color the first $$$3$$$ sticks of length $$$1$$$ with the color $$$1$$$, and all other sticks with the color $$$2$$$.

It can be shown that it's not possible to color the sticks with only one color (since then it would be possible to form a square using sticks of length $$$1$$$).