MEPhI Аutumn Cup 2025
A. Simulation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While creating large language models, a group of researchers decided to conduct a partial simulation of the processes occurring during machine learning. They divided this task into many parts, and one of them has been assigned to you.

You are given an array $$$a$$$ of length $$$n$$$. You need to calculate an array $$$b$$$ of length $$$n$$$ such that $$$b_i = a_i$$$ if for any $$$j \lt i$$$ it holds that $$$a_j \ne a_i$$$, and $$$b_i = a_i + 1$$$ otherwise.

Input

The first line of input contains the number $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

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

Output

In a single line, output the array $$$b_1, b_2, \ldots, b_n$$$ – the answer to the problem.

Examples
Input
4
1 1 2 1
Output
1 2 2 2 
Input
5
1 4 2 3 1
Output
1 4 2 3 2 

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

While studying the characteristics of a device of one of the neural networks, Mark identified a certain array $$$a$$$, which he obtained after transforming the network parameters. Moreover, he ensured that this array is somehow related to the efficiency of the network. However, he is not sure how this array changes during the further training process. Mark assumes that during the training process, the array can only change by one type of operation. To verify this, he launched the training process and obtained a new array $$$b$$$. Now he asks you to help verify his hypothesis.

You are given an array $$$a$$$. You can perform the following operation on it any number of times: choose an element of the array $$$x$$$ and replace it with 2 elements of value $$$x + 1$$$ at that position. The length of the array increases by 1 in this case.

You need to determine if it is possible to obtain array $$$b$$$.

Input

The first line of the input contains the numbers $$$n, m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$).

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

The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m\, (1\le b_i \le 10^9)$$$ — the values of the elements of array $$$b$$$.

Output

If it is possible to obtain array $$$b$$$ from array $$$a$$$, then output «Yes», otherwise output «No».

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

C. Table Tennis
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While playing table tennis, Andrew-13 wondered if it is possible to finish the game exactly after round $$$x$$$.

Regular table tennis continues until one of the players scores at least 11 points with a lead of at least 2 points over the other player, but games with such rules can end quickly. Therefore, Andrew-13 decided to consider tennis where the game continues until one of the players scores at least $$$n$$$ points with a lead of at least $$$k$$$ points.

Initially, each player has $$$0$$$ points. Then the game rounds begin. Each round ends with one of the two players winning (there are no draws), who receives $$$+1$$$ point. As soon as one of the players has at least $$$n$$$ points and is at least $$$k$$$ points ahead of the opponent, the game ends.

You need to determine for $$$t$$$ possible parameters $$$n, k$$$, and $$$x$$$, whether the game can end exactly after round $$$x$$$ (rounds are numbered starting from $$$1$$$).

Input

The first line of input contains the number $$$t\, (1 \le t \le 10^3)$$$ – the number of possible parameters.

Each of the following $$$t$$$ lines contains three numbers $$$n, k, x$$$ $$$(1 \le n, k, x \le 10^9)$$$.

Output

For each set of input data, output «Yes» on a separate line if the game can end exactly after round $$$x$$$; otherwise, output «No».

Example
Input
5
11 2 13
11 2 21
1 1 100
10 2 17
2 3 998244353
Output
Yes
No
No
Yes
Yes

D. String Automaton
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently, you found an interesting machine that turned out to be a string automaton. This device defines a certain set of valid strings and, for a specific string, indicates whether that string belongs to its alphabet.

After some time, you figured out the structure of the automaton – it has $$$n$$$ vertices and $$$m$$$ directed edges between them. Each edge is labeled with a letter from the Latin alphabet, and some vertices are terminal. The graph may contain loops and multiple edges.

The automaton considers a string of Latin characters to be $$$valid$$$ if the following process can end in a terminal vertex.

Initially, $$$x = 1$$$ – the current state. Then, the characters of the string are considered one by one. If there is no transition from the current vertex for the next character $$$s$$$, the process ends, and the string is considered invalid. If there are transitions for the character $$$s$$$, the state changes to one of the states reachable from $$$x$$$ by the letter $$$s$$$.

Note that there may be multiple transitions from one vertex for the letter $$$s$$$, but for the string to be considered valid, it is sufficient that at least one path ends in a terminal vertex.

Additionally, the empty string is considered $$$valid$$$ regardless of the structure of the automaton.

You need to determine the maximum length of a string that is $$$valid$$$.

If the length is finite, you should output the lexicographically smallest string of maximum length.

For strings of the same length $$$S, T$$$ $$$(S \ne T)$$$, $$$S$$$ is called lexicographically smaller than $$$T$$$ if there exists an $$$i$$$ such that for $$$j$$$ ($$$1 \le j \lt i$$$) $$$S_{j} = T_j$$$ and $$$S_{i} \lt T_i$$$.

Input

The first line contains the numbers $$$n, m$$$, and $$$k$$$ ($$$1 \le n, m, k \le 5 \cdot 10^5$$$) – the number of vertices, edges in the automaton, and the number of terminal vertices.

The next $$$m$$$ lines contain 3 numbers $$$u, v, s$$$, indicating that there is a directed edge from $$$u$$$ to $$$v$$$ with the letter $$$s$$$ $$$(1 \le u,v \le n)$$$, where $$$s$$$ is a character from the Latin alphabet.

The following line contains $$$k$$$ numbers $$$u_1, u_2, \ldots, u_k\, (1\le u_i \le n)$$$ – the terminal vertices.

Output

In the first line, output «inf» if there exist infinitely long $$$valid$$$ strings.

Otherwise, output the length of the longest $$$valid$$$ string, and in the next line, output the lexicographically smallest string that is $$$valid$$$.

Examples
Input
4 4 2
1 2 a
2 3 b
1 3 b
4 4 a
3 4
Output
2
ab
Input
3 4 1
1 2 a
1 3 c
3 2 c
2 2 a
3
Output
1
c

E. Leaf
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 joined a group of researchers working on neural networks. A neural network is represented as a graph, where the vertices correspond to neurons and the edges represent connections between them. To demonstrate your skills in working with graphs, you need to solve the following problem.

You are given a directed graph with $$$n$$$ vertices, without loops and multiple edges, but you do not know the structure of this graph. You need to find a leaf in this graph or determine that there are no leaves in it (a leaf is defined as a vertex connected to exactly one other vertex, disregarding the orientation of the edges).

To obtain information about the graph, you can make queries. In each query, you can choose sets $$$S$$$ and $$$T$$$, which are subsets of {$$$1, 2, \ldots n$$$}. In response, you will receive the number of edges that start at one of the vertices in set $$$S$$$ and end at one of the vertices in set $$$T$$$ (considering the orientation of the edges). The sets $$$S$$$ and $$$T$$$ may overlap.

You can make no more than $$$n$$$ queries. At any moment, you can output the answer to the problem – the index of the vertex that is a leaf, or $$$-1$$$ if there are no leaves in the graph.

Interaction

The first line contains the number $$$t$$$ ($$$1 \le t \le 100$$$) – the number of tests.

In each test, the number $$$n$$$ ($$$1 \le n \le 100$$$) is given – the number of vertices in the graph. It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$1000$$$.

Next, your program can choose sets $$$S$$$ = {$$$s_1, s_2, \ldots, s_k$$$} and $$$T$$$ = {$$$t_1, t_2, \ldots, t_r$$$} and output «? $$$k$$$ $$$s_1$$$ $$$s_2 \ldots s_k$$$ $$$r$$$ $$$t_1$$$ $$$t_2 \ldots t_r$$$». After that, you will receive the number of edges that start at one of the vertices in set $$$S$$$ and end at one of the vertices in set $$$T$$$. Note that there should be no extra spaces after the last number in the query.

As soon as the program is ready to provide an answer, you can output «! $$$x$$$», where $$$x$$$ is $$$-1$$$ if no leaf exists, or the index of the leaf otherwise (indexing starts from $$$1$$$). The program should then proceed to process the next test or terminate if this was the last test.

If you make more than $$$n$$$ queries during the interaction, your program should terminate immediately, and you will receive a Wrong Answer verdict. Otherwise, you may receive an arbitrary verdict.

After each query output, do not forget to output a newline and flush the output buffer. Otherwise, you will receive a verdict of Solution stuck. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
Example
Input
2
3

1

2

2

Output


? 1 1 2 2 3

? 2 1 2 2 2 3

! 1

! -1
Note

In the first example, there are only 2 edges in the graph – 1→2 and 2→3.

In the second example, the graph is empty.

This example is given to illustrate the interaction with the interactor; it does not guarantee the possibility of finding an answer based on the given queries.

F. Bracket Sequences
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After studying linear algebra for machine learning, Leonid decided to return to discrete problems. One of them he liked so much that he decided to share it with you.

There is an array of non-zero integers $$$a_1, a_2, \ldots, a_n$$$, where a positive number $$$x$$$ in the array corresponds to $$$x$$$ opening brackets, and a negative number corresponds to $$$-x$$$ closing brackets. For example, the array [3, -2] corresponds to ((()).

A subarray $$$a_l, a_{l+1}, \ldots, a_r$$$, where $$$(l \le r)$$$ is called $$$good$$$ if its elements can be rearranged to form an array $$$b_1, b_2, \ldots, b_{r-l+1}$$$ such that the corresponding bracket sequence is balanced and there is at least one negative number among any two consecutive elements of the array $$$b$$$.

For the given array $$$a$$$, you need to count the number of its $$$good$$$ subarrays.

A bracket sequence is called balanced if it can be turned into a correct mathematical expression by adding the symbols + and 1.

Input

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

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

Output

In a single line, output one number – the answer to the problem.

Example
Input
5
3 -1 2 -2 1
Output
2

G. Series of Victories
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Andrey and Sasha love to play table tennis and have already played many matches. Since games under the usual rules ended very quickly, they decided to play until one of them scores $$$n$$$ points and has a lead of $$$k$$$ points.

The game proceeds as follows. Initially, each player has $$$0$$$ points. Then the game rounds begin. Each round ends with one of the two players winning (there can be no draws). As soon as one of the players has at least $$$n$$$ points and is at least $$$k$$$ points ahead of the opponent, the game ends.

Andrey and Sasha have played many games against each other. However, information about some of them has been lost. Andrey remembers that a total of $$$g$$$ rounds were played, and he won between $$$l$$$ and $$$l+13$$$ rounds. If he won $$$x$$$ rounds, it can be assumed that the probability of Andrey winning each round is constant and equal to $$$x/g$$$. This probability also does not change during the subsequent games.

Andrey became curious about the probability that he can win $$$s$$$ rounds in a row regardless of the outcome of the game. Since he does not remember the exact value of $$$x$$$, he wants to calculate this probability for any of the permissible $$$x$$$.

The answer must be output modulo $$$998244353$$$.

Input

The first line contains 3 integers $$$n, k$$$, and $$$s$$$, ($$$1 \le n \le 3000$$$), ($$$1 \le k \le 300$$$), ($$$1 \le s \le 3000$$$).

The second line contains 2 integers $$$g$$$ and $$$l$$$ ($$$100 \le g \le 10^8$$$), ($$$0 \le l \le g - 13$$$) – the number of rounds played and the minimum number of rounds won by Andrey.

Output

In a single line, output 2 numbers $$$x$$$ and $$$p$$$ – the chosen number of rounds won ($$$l \le x \le l + 13$$$) and the sought probability for this $$$x$$$ modulo $$$998244353$$$.

Examples
Input
3 1 2
300 100
Output
100 242372086
Input
100 50 50
652 356
Output
365 964566959