apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an integer $$$n$$$. You have to construct a permutation of size $$$n$$$.

A permutation is an array where each integer from $$$1$$$ to $$$s$$$ (where $$$s$$$ is the size of permutation) occurs exactly once. For example, $$$[2, 1, 4, 3]$$$ is a permutation of size $$$4$$$; $$$[1, 2, 4, 5, 3]$$$ is a permutation of size $$$5$$$; $$$[1, 4, 3]$$$ is not a permutation (the integer $$$2$$$ is absent), $$$[2, 1, 3, 1]$$$ is not a permutation (the integer $$$1$$$ appears twice).

A subsegment of a permutation is a contiguous subsequence of that permutation. For example, the permutation $$$[2, 1, 4, 3]$$$ has $$$10$$$ subsegments: $$$[2]$$$, $$$[2, 1]$$$, $$$[2, 1, 4]$$$, $$$[2, 1, 4, 3]$$$, $$$[1]$$$, $$$[1, 4]$$$, $$$[1, 4, 3]$$$, $$$[4]$$$, $$$[4, 3]$$$ and $$$[3]$$$.

The value of the permutation is the number of its subsegments which are also permutations. For example, the value of $$$[2, 1, 4, 3]$$$ is $$$3$$$ since the subsegments $$$[2, 1]$$$, $$$[1]$$$ and $$$[2, 1, 4, 3]$$$ are permutations.

You have to construct a permutation of size $$$n$$$ with minimum possible value among all permutations of size $$$n$$$.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 48$$$) — the number of test cases.

Then, $$$t$$$ lines follow. The $$$i$$$-th of them contains one integer $$$n$$$ ($$$3 \le n \le 50$$$) representing the $$$i$$$-th test case.

## Output Format
For each test case, print $$$n$$$ integers — the permutation of size $$$n$$$ with minimum possible value. If there are multiple such permutations, print any of them.

## Examples
```input
2
5
6
```
```output
1 4 3 5 2
4 1 6 2 5 3
```

## Note
In the first example, the permutation $$$[1, 4, 3, 5, 2]$$$ is one of the possible answers; its value is $$$2$$$.

In the second example, the permutation $$$[4, 1, 6, 2, 5, 3]$$$ is one of the possible answers; its value is $$$2$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a string $$$s$$$ consisting of $$$n$$$ characters. Each character of $$$s$$$ is either 0 or 1.

A substring of $$$s$$$ is a contiguous subsequence of its characters.

You have to choose two substrings of $$$s$$$ (possibly intersecting, possibly the same, possibly non-intersecting — just any two substrings). After choosing them, you calculate the value of the chosen pair of substrings as follows:

- let $$$s_1$$$ be the first substring, $$$s_2$$$ be the second chosen substring, and $$$f(s_i)$$$ be the integer such that $$$s_i$$$ is its binary representation (for example, if $$$s_i$$$ is 11010, $$$f(s_i) = 26$$$);
- the value is the bitwise OR of $$$f(s_1)$$$ and $$$f(s_2)$$$.

Calculate the maximum possible value you can get, and print it in binary representation without leading zeroes.

## Input Format
The first line contains one integer $$$n$$$ — the number of characters in $$$s$$$.

The second line contains $$$s$$$ itself, consisting of exactly $$$n$$$ characters 0 and/or 1.

All non-example tests in this problem are generated randomly: every character of $$$s$$$ is chosen independently of other characters; for each character, the probability of it being 1 is exactly $$$\frac{1}{2}$$$.

This problem has exactly $$$40$$$ tests. Tests from $$$1$$$ to $$$3$$$ are the examples; tests from $$$4$$$ to $$$40$$$ are generated randomly. In tests from $$$4$$$ to $$$10$$$, $$$n = 5$$$; in tests from $$$11$$$ to $$$20$$$, $$$n = 1000$$$; in tests from $$$21$$$ to $$$40$$$, $$$n = 10^6$$$.

Hacks are forbidden in this problem.

## Output Format
Print the maximum possible value you can get in binary representation without leading zeroes.

## Examples
```input
5
11010
```
```output
11111
```
-----
```input
7
1110010
```
```output
1111110
```
-----
```input
4
0000
```
```output
0
```

## Note
In the first example, you can choose the substrings 11010 and 101. $$$f(s_1) = 26$$$, $$$f(s_2) = 5$$$, their bitwise OR is $$$31$$$, and the binary representation of $$$31$$$ is 11111.

In the second example, you can choose the substrings 1110010 and 11100.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 512.0 MB

# Problem
Monocarp is playing a video game. In the game, he controls a spaceship and has to destroy an enemy spaceship.

Monocarp has two lasers installed on his spaceship. Both lasers $$$1$$$ and $$$2$$$ have two values:

- $$$p_i$$$ — the power of the laser;
- $$$t_i$$$ — the reload time of the laser.

When a laser is fully charged, Monocarp can either shoot it or wait for the other laser to charge and shoot both of them at the same time.

An enemy spaceship has $$$h$$$ durability and $$$s$$$ shield capacity. When Monocarp shoots an enemy spaceship, it receives $$$(P - s)$$$ damage (i. e. $$$(P - s)$$$ gets subtracted from its durability), where $$$P$$$ is the total power of the lasers that Monocarp shoots (i. e. $$$p_i$$$ if he only shoots laser $$$i$$$ and $$$p_1 + p_2$$$ if he shoots both lasers at the same time). An enemy spaceship is considered destroyed when its durability becomes $$$0$$$ or lower.

Initially, both lasers are zero charged.

What's the lowest amount of time it can take Monocarp to destroy an enemy spaceship?

## Input Format
The first line contains two integers $$$p_1$$$ and $$$t_1$$$ ($$$2 \le p_1 \le 5000$$$; $$$1 \le t_1 \le 10^{12}$$$) — the power and the reload time of the first laser.

The second line contains two integers $$$p_2$$$ and $$$t_2$$$ ($$$2 \le p_2 \le 5000$$$; $$$1 \le t_2 \le 10^{12}$$$) — the power and the reload time of the second laser.

The third line contains two integers $$$h$$$ and $$$s$$$ ($$$1 \le h \le 5000$$$; $$$1 \le s < \min(p_1, p_2)$$$) — the durability and the shield capacity of an enemy spaceship. Note that the last constraint implies that Monocarp will always be able to destroy an enemy spaceship.

## Output Format
Print a single integer — the lowest amount of time it can take Monocarp to destroy an enemy spaceship.

## Examples
```input
5 10
4 9
16 1
```
```output
20
```
-----
```input
10 1
5000 100000
25 9
```
```output
25
```

## Note
In the first example, Monocarp waits for both lasers to charge, then shoots both lasers at $$$10$$$, they deal $$$(5 + 4 - 1) = 8$$$ damage. Then he waits again and shoots lasers at $$$20$$$, dealing $$$8$$$ more damage.

In the second example, Monocarp doesn't wait for the second laser to charge. He just shoots the first laser $$$25$$$ times, dealing $$$(10 - 9) = 1$$$ damage each time.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 5.0 seconds
Memory limit: 512.0 MB

# Problem
You are given $$$n$$$ segments on the coordinate axis. The $$$i$$$-th segment is $$$[l_i, r_i]$$$. Let's denote the set of all integer points belonging to the $$$i$$$-th segment as $$$S_i$$$.

Let $$$A \cup B$$$ be the union of two sets $$$A$$$ and $$$B$$$, $$$A \cap B$$$ be the intersection of two sets $$$A$$$ and $$$B$$$, and $$$A \oplus B$$$ be the symmetric difference of $$$A$$$ and $$$B$$$ (a set which contains all elements of $$$A$$$ and all elements of $$$B$$$, except for the ones that belong to both sets).

Let $$$[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}]$$$ be an array where each element is either $$$\cup$$$, $$$\oplus$$$, or $$$\cap$$$. Over all $$$3^{n-1}$$$ ways to choose this array, calculate the sum of the following values:

$$$$$$|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$$$$$$

In this expression, $$$|S|$$$ denotes the size of the set $$$S$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$).

Then, $$$n$$$ lines follow. The $$$i$$$-th of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i \le r_i \le 3 \cdot 10^5$$$).

## Output Format
Print one integer — the sum of $$$|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$$$ over all possible ways to choose $$$[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}]$$$. Since the answer can be huge, print it modulo $$$998244353$$$.

## Examples
```input
4
3 5
4 8
2 2
1 9
```
```output
162
```
-----
```input
4
1 9
3 5
4 8
2 2
```
```output
102
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Let's call a positive integer extremely round if it has only one non-zero digit. For example, $$$5000$$$, $$$4$$$, $$$1$$$, $$$10$$$, $$$200$$$ are extremely round integers; $$$42$$$, $$$13$$$, $$$666$$$, $$$77$$$, $$$101$$$ are not.

You are given an integer $$$n$$$. You have to calculate the number of extremely round integers $$$x$$$ such that $$$1 \le x \le n$$$.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Then, $$$t$$$ lines follow. The $$$i$$$-th of them contains one integer $$$n$$$ ($$$1 \le n \le 999999$$$) — the description of the $$$i$$$-th test case.

## Output Format
For each test case, print one integer — the number of extremely round integers $$$x$$$ such that $$$1 \le x \le n$$$.

## Examples
```input
5
9
42
13
100
111
```
```output
9
13
10
19
19
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a graph consisting of $$$n$$$ vertices and $$$m$$$ directed arcs. The $$$i$$$-th arc goes from the vertex $$$x_i$$$ to the vertex $$$y_i$$$, has capacity $$$c_i$$$ and weight $$$w_i$$$. No arc goes into the vertex $$$1$$$, and no arc goes from the vertex $$$n$$$. There are no cycles of negative weight in the graph (it is impossible to travel from any vertex to itself in such a way that the total weight of all arcs you go through is negative).

You have to assign each arc a flow (an integer between $$$0$$$ and its capacity, inclusive). For every vertex except $$$1$$$ and $$$n$$$, the total flow on the arcs going to this vertex must be equal to the total flow on the arcs going from that vertex. Let the flow on the $$$i$$$-th arc be $$$f_i$$$, then the cost of the flow is equal to $$$\sum \limits_{i = 1}^{m} f_i w_i$$$. You have to find a flow which minimizes the cost.

Sounds classical, right? Well, we have some additional constraints on the flow on every edge:

- if $$$c_i$$$ is even, $$$f_i$$$ must be even;
- if $$$c_i$$$ is odd, $$$f_i$$$ must be odd.

Can you solve this problem?

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 100$$$; $$$1 \le m \le 200$$$).

Then $$$m$$$ lines follow. The $$$i$$$-th of them contains four integers $$$x_i$$$, $$$y_i$$$, $$$c_i$$$, and $$$w_i$$$ ($$$1 \le x_i \le n - 1$$$; $$$2 \le y_i \le n$$$; $$$x_i \ne y_i$$$; $$$1 \le c_i \le 100$$$; $$$-100 \le w_i \le 100$$$). These integers describe the $$$i$$$-th arc.

Additional constraints on the input:

- there are no negative cycles in the graph.

## Output Format
If a flow satisfying all of the constraints does not exist, print Impossible.

Otherwise, print two lines:

- the first line should contain one word Possible;
- the second line should contain $$$m$$$ integers $$$f_1, f_2, \dots, f_m$$$.

If there are multiple answers, print any of them. Note that the cost of the flow should be minimized.

## Examples
```input
3 3
1 2 3 -10
1 2 3 -15
2 3 2 0
```
```output
Possible
1 1 2
```
-----
```input
3 3
1 2 3 -10
1 2 3 -15
2 3 3 0
```
```output
Impossible
```
-----
```input
3 3
1 2 3 -10
1 2 3 -15
2 3 4 0
```
```output
Possible
1 3 4
```
-----
```input
6 7
5 6 9 -40
1 2 3 -10
1 4 5 20
4 5 7 30
2 5 1 -15
1 3 3 5
3 5 3 0
```
```output
Possible
5 1 1 1 1 3 3
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an expression of the form $$$a{+}b$$$, where $$$a$$$ and $$$b$$$ are integers from $$$0$$$ to $$$9$$$. You have to evaluate it and print the result.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

Each test case consists of one line containing an expression of the form $$$a{+}b$$$ ($$$0 \le a, b \le 9$$$, both $$$a$$$ and $$$b$$$ are integers). The integers are not separated from the $$$+$$$ sign.

## Output Format
For each test case, print one integer — the result of the expression.

## Examples
```input
4
4+2
0+0
3+7
8+9
```
```output
6
0
10
17
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You have a matrix $$$2 \times 2$$$ filled with distinct integers. You want your matrix to become beautiful. The matrix is beautiful if the following two conditions are satisfied:

- in each row, the first element is smaller than the second element;
- in each column, the first element is smaller than the second element.

You can perform the following operation on the matrix any number of times: rotate it clockwise by $$$90$$$ degrees, so the top left element shifts to the top right cell, the top right element shifts to the bottom right cell, and so on:

Determine if it is possible to make the matrix beautiful by applying zero or more operations.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case consists of two lines. Each of those lines contains two integers — the elements of the corresponding row of the matrix. In each matrix, all four elements are distinct integers from $$$1$$$ to $$$100$$$.

## Output Format
For each test case, print YES if the matrix can become beautiful, or NO otherwise. You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

## Examples
```input
6
1 3
5 7
8 10
3 4
8 10
4 3
6 1
9 2
7 5
4 2
1 2
4 3
```
```output
YES
YES
NO
YES
YES
NO
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
An array $$$a$$$ consisting of $$$k$$$ integers is strictly increasing if $$$a_1 < a_2 < \dots < a_k$$$. For example, the arrays $$$[1, 3, 5]$$$, $$$[1, 2, 3, 4]$$$, $$$[3, 5, 6]$$$ are strictly increasing; the arrays $$$[2, 2]$$$, $$$[3, 7, 5]$$$, $$$[7, 4, 3]$$$, $$$[1, 2, 2, 3]$$$ are not.

For a strictly increasing array $$$a$$$ of $$$k$$$ elements, let's denote the characteristic as the number of different elements in the array $$$[a_2 - a_1, a_3 - a_2, \dots, a_k - a_{k-1}]$$$. For example, the characteristic of the array $$$[1, 3, 4, 7, 8]$$$ is $$$3$$$ since the array $$$[2, 1, 3, 1]$$$ contains $$$3$$$ different elements: $$$2$$$, $$$1$$$ and $$$3$$$.

You are given two integers $$$k$$$ and $$$n$$$ ($$$k \le n$$$). Construct an increasing array of $$$k$$$ integers from $$$1$$$ to $$$n$$$ with maximum possible characteristic.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 819$$$) — the number of test cases.

Each test case consists of one line containing two integers $$$k$$$ and $$$n$$$ ($$$2 \le k \le n \le 40$$$).

## Output Format
For each test case, print $$$k$$$ integers — the elements of the strictly increasing array $$$a$$$ with the maximum possible characteristic. If there are multiple answers, print any of them.

## Examples
```input
7
5 9
4 12
3 3
3 4
4 4
4 6
8 11
```
```output
1 3 4 7 8
2 4 7 12
1 2 3
1 3 4
1 2 3 4
2 4 5 6
1 2 3 5 6 7 8 11
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ integers. The array is sorted if $$$a_1 \le a_2 \le \dots \le a_n$$$.

You want to make the array $$$a$$$ sorted by applying the following operation exactly once:

- choose an integer $$$x$$$, then for every $$$i \in [1, n]$$$, replace $$$a_i$$$ by $$$|a_i - x|$$$.

Find any value of $$$x$$$ that will make the array sorted, or report that there is no such value.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases.

Each test case consists of two lines. The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$). The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^8$$$).

Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print any integer $$$x$$$ ($$$0 \le x \le 10^9$$$) that makes the array sorted. It can be shown that if such an integer $$$x$$$ exists, there is at least one such integer between $$$0$$$ and $$$10^9$$$.

If there is no such integer, then print $$$-1$$$. If there are multiple suitable values of $$$x$$$, print any of them.

## Examples
```input
8
5
5 3 3 3 5
4
5 3 4 5
8
1 2 3 4 5 6 7 8
6
10 5 4 3 2 1
3
3 3 1
3
42 43 42
2
100000000 99999999
6
29613295 52036613 75100585 78027446 81409090 73215
```
```output
4
-1
0
42
2
-1
100000000
40741153
```

## Note
In the first test case, after using $$$x = 4$$$, the array becomes $$$[1, 1, 1, 1, 1]$$$.

In the third test case, after using $$$x = 0$$$, the array becomes $$$[1, 2, 3, 4, 5, 6, 7, 8]$$$.

In the fourth test case, after using $$$x = 42$$$, the array becomes $$$[32, 37, 38, 39, 40, 41]$$$.

Now solve the problem and return the code.