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 python3.

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:
```python
<your code here>
```

Execution time limit: 4.5 seconds
Memory limit: 768.0 MB

# Problem
A tree is a connected undirected graph without cycles. A weighted tree has a weight assigned to each edge. The degree of a vertex is the number of edges connected to this vertex.

You are given a weighted tree with $$$n$$$ vertices, each edge has a weight of $$$1$$$. Let $$$L$$$ be the set of vertices with degree equal to $$$1$$$.

You have to answer $$$q$$$ independent queries. In the $$$i$$$-th query:

1. You are given a positive integer $$$x_i$$$.
2. For all $$$u,v \in L$$$ such that $$$u < v$$$, add edge $$$(u, v)$$$ with weight $$$x_i$$$ to the graph (initially the given tree).
3. Find the diameter of the resulting graph.

The diameter of a graph is equal to $$$\max\limits_{1 \le u < v \le n}{\operatorname{d}(u, v)}$$$, where $$$\operatorname{d}(u, v)$$$ is the length of the shortest path between vertex $$$u$$$ and vertex $$$v$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$3 \le n \le 10^6$$$).

The second line contains $$$n - 1$$$ integers $$$p_2,p_3,\ldots,p_n$$$ ($$$1 \le p_i < i$$$) indicating that there is an edge between vertices $$$i$$$ and $$$p_i$$$. It is guaranteed that the given edges form a tree.

The third line contains a single integer $$$q$$$ ($$$1 \le q \le 10$$$).

The fourth line contains $$$q$$$ integers $$$x_1,x_2,\ldots,x_q$$$ ($$$1 \le x_i \le n$$$). All $$$x_i$$$ are distinct.

## Output Format
Print $$$q$$$ integers in a single line — the answers to the queries.

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

## Note
The graph in the first test after adding the edges:

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are standing at the point $$$0$$$ on a coordinate line. Your goal is to reach the point $$$n$$$. In one minute, you can move by $$$2$$$ or by $$$3$$$ to the left or to the right (i. e., if your current coordinate is $$$x$$$, it can become $$$x-3$$$, $$$x-2$$$, $$$x+2$$$ or $$$x+3$$$). Note that the new coordinate can become negative.

Your task is to find the minimum number of minutes required to get from the point $$$0$$$ to the point $$$n$$$.

You have to answer $$$t$$$ independent test cases.

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

The $$$i$$$-th of these lines contains one integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — the goal of the $$$i$$$-th test case.

## Output Format
For each test case, print one integer — the minimum number of minutes required to get from the point $$$0$$$ to the point $$$n$$$ for the corresponding test case.

## Examples
```input
4
1
3
4
12
```
```output
2
1
2
4
```

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
There is a grid, consisting of $$$2$$$ rows and $$$m$$$ columns. The rows are numbered from $$$1$$$ to $$$2$$$ from top to bottom. The columns are numbered from $$$1$$$ to $$$m$$$ from left to right.

The robot starts in a cell $$$(1, 1)$$$. In one second, it can perform either of two actions:

- move into a cell adjacent by a side: up, right, down or left;
- remain in the same cell.

The robot is not allowed to move outside the grid.

Initially, all cells, except for the cell $$$(1, 1)$$$, are locked. Each cell $$$(i, j)$$$ contains a value $$$a_{i,j}$$$ — the moment that this cell gets unlocked. The robot can only move into a cell $$$(i, j)$$$ if at least $$$a_{i,j}$$$ seconds have passed before the move.

The robot should visit all cells without entering any cell twice or more (cell $$$(1, 1)$$$ is considered entered at the start). It can finish in any cell.

What is the fastest the robot can achieve that?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$m$$$ ($$$2 \le m \le 2 \cdot 10^5$$$) — the number of columns of the grid.

The $$$i$$$-th of the next $$$2$$$ lines contains $$$m$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$0 \le a_{i,j} \le 10^9$$$) — the moment of time each cell gets unlocked. $$$a_{1,1} = 0$$$. If $$$a_{i,j} = 0$$$, then cell $$$(i, j)$$$ is unlocked from the start.

The sum of $$$m$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print a single integer — the minimum amount of seconds that the robot can take to visit all cells without entering any cell twice or more.

## Examples
```input
4
3
0 0 1
4 3 2
5
0 4 8 12 16
2 6 10 14 18
4
0 10 10 10
10 10 10 10
2
0 0
0 0
```
```output
5
19
17
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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
There is a chip on the coordinate line. Initially, the chip is located at the point $$$0$$$. You can perform any number of moves; each move increases the coordinate of the chip by some positive integer (which is called the length of the move). The length of the first move you make should be divisible by $$$k$$$, the length of the second move — by $$$k+1$$$, the third — by $$$k+2$$$, and so on.

For example, if $$$k=2$$$, then the sequence of moves may look like this: $$$0 \rightarrow 4 \rightarrow 7 \rightarrow 19 \rightarrow 44$$$, because $$$4 - 0 = 4$$$ is divisible by $$$2 = k$$$, $$$7 - 4 = 3$$$ is divisible by $$$3 = k + 1$$$, $$$19 - 7 = 12$$$ is divisible by $$$4 = k + 2$$$, $$$44 - 19 = 25$$$ is divisible by $$$5 = k + 3$$$.

You are given two positive integers $$$n$$$ and $$$k$$$. Your task is to count the number of ways to reach the point $$$x$$$, starting from $$$0$$$, for every $$$x \in [1, n]$$$. The number of ways can be very large, so print it modulo $$$998244353$$$. Two ways are considered different if they differ as sets of visited positions.

## Input Format
The first (and only) line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).

## Output Format
Print $$$n$$$ integers — the number of ways to reach the point $$$x$$$, starting from $$$0$$$, for every $$$x \in [1, n]$$$, taken modulo $$$998244353$$$.

## Examples
```input
8 1
```
```output
1 1 2 2 3 4 5 6
```
-----
```input
10 2
```
```output
0 1 0 1 1 1 1 2 2 2
```

## Note
Let's look at the first example:

Ways to reach the point $$$1$$$: $$$[0, 1]$$$;

Ways to reach the point $$$2$$$: $$$[0, 2]$$$;

Ways to reach the point $$$3$$$: $$$[0, 1, 3]$$$, $$$[0, 3]$$$;

Ways to reach the point $$$4$$$: $$$[0, 2, 4]$$$, $$$[0, 4]$$$;

Ways to reach the point $$$5$$$: $$$[0, 1, 5]$$$, $$$[0, 3, 5]$$$, $$$[0, 5]$$$;

Ways to reach the point $$$6$$$: $$$[0, 1, 3, 6]$$$, $$$[0, 2, 6]$$$, $$$[0, 4, 6]$$$, $$$[0, 6]$$$;

Ways to reach the point $$$7$$$: $$$[0, 2, 4, 7]$$$, $$$[0, 1, 7]$$$, $$$[0, 3, 7]$$$, $$$[0, 5, 7]$$$, $$$[0, 7]$$$;

Ways to reach the point $$$8$$$: $$$[0, 3, 5, 8]$$$, $$$[0, 1, 5, 8]$$$, $$$[0, 2, 8]$$$, $$$[0, 4, 8]$$$, $$$[0, 6, 8]$$$, $$$[0, 8]$$$.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an array of length $$$2^n$$$. The elements of the array are numbered from $$$1$$$ to $$$2^n$$$.

You have to process $$$q$$$ queries to this array. In the $$$i$$$-th query, you will be given an integer $$$k$$$ ($$$0 \le k \le n-1$$$). To process the query, you should do the following:

- for every $$$i \in [1, 2^n-2^k]$$$ in ascending order, do the following: if the $$$i$$$-th element was already swapped with some other element during this query, skip it; otherwise, swap $$$a_i$$$ and $$$a_{i+2^k}$$$;
- after that, print the maximum sum over all contiguous subsegments of the array (including the empty subsegment).

For example, if the array $$$a$$$ is $$$[-3, 5, -3, 2, 8, -20, 6, -1]$$$, and $$$k = 1$$$, the query is processed as follows:

- the $$$1$$$-st element wasn't swapped yet, so we swap it with the $$$3$$$-rd element;
- the $$$2$$$-nd element wasn't swapped yet, so we swap it with the $$$4$$$-th element;
- the $$$3$$$-rd element was swapped already;
- the $$$4$$$-th element was swapped already;
- the $$$5$$$-th element wasn't swapped yet, so we swap it with the $$$7$$$-th element;
- the $$$6$$$-th element wasn't swapped yet, so we swap it with the $$$8$$$-th element.

So, the array becomes $$$[-3, 2, -3, 5, 6, -1, 8, -20]$$$. The subsegment with the maximum sum is $$$[5, 6, -1, 8]$$$, and the answer to the query is $$$18$$$.

Note that the queries actually change the array, i. e. after a query is performed, the array does not return to its original state, and the next query will be applied to the modified array.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 18$$$).

The second line contains $$$2^n$$$ integers $$$a_1, a_2, \dots, a_{2^n}$$$ ($$$-10^9 \le a_i \le 10^9$$$).

The third line contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$).

Then $$$q$$$ lines follow, the $$$i$$$-th of them contains one integer $$$k$$$ ($$$0 \le k \le n-1$$$) describing the $$$i$$$-th query.

## Output Format
For each query, print one integer — the maximum sum over all contiguous subsegments of the array (including the empty subsegment) after processing the query.

## Examples
```input
3
-3 5 -3 2 8 -20 6 -1
3
1
0
1
```
```output
18
8
13
```

## Note
Transformation of the array in the example: $$$[-3, 5, -3, 2, 8, -20, 6, -1] \rightarrow [-3, 2, -3, 5, 6, -1, 8, -20] \rightarrow [2, -3, 5, -3, -1, 6, -20, 8] \rightarrow [5, -3, 2, -3, -20, 8, -1, 6]$$$.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
There are $$$n$$$ bags, each bag contains $$$m$$$ balls with numbers from $$$1$$$ to $$$m$$$. For every $$$i \in [1, m]$$$, there is exactly one ball with number $$$i$$$ in each bag.

You have to take exactly one ball from each bag (all bags are different, so, for example, taking the ball $$$1$$$ from the first bag and the ball $$$2$$$ from the second bag is not the same as taking the ball $$$2$$$ from the first bag and the ball $$$1$$$ from the second bag). After that, you calculate the number of balls with odd numbers among the ones you have taken. Let the number of these balls be $$$F$$$.

Your task is to calculate the sum of $$$F^k$$$ over all possible ways to take $$$n$$$ balls, one from each bag.

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

Each test case consists of one line containing three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n, m \le 998244352$$$; $$$1 \le k \le 2000$$$).

## Output Format
For each test case, print one integer — the sum of $$$F^k$$$ over all possible ways to take $$$n$$$ balls, one from each bag. Since it can be huge, print it modulo $$$998244353$$$.

## Examples
```input
5
2 3 8
1 1 1
1 5 10
3 7 2000
1337666 42424242 2000
```
```output
1028
1
3
729229716
652219904
```

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Vlad went into his appartment house entrance, now he is on the $$$1$$$-th floor. He was going to call the elevator to go up to his apartment.

There are only two elevators in his house. Vlad knows for sure that:

- the first elevator is currently on the floor $$$a$$$ (it is currently motionless),
- the second elevator is located on floor $$$b$$$ and goes to floor $$$c$$$ ($$$b \ne c$$$). Please note, if $$$b=1$$$, then the elevator is already leaving the floor $$$1$$$ and Vlad does not have time to enter it.

If you call the first elevator, it will immediately start to go to the floor $$$1$$$. If you call the second one, then first it will reach the floor $$$c$$$ and only then it will go to the floor $$$1$$$. It takes $$$|x - y|$$$ seconds for each elevator to move from floor $$$x$$$ to floor $$$y$$$.

Vlad wants to call an elevator that will come to him faster. Help him choose such an elevator.

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

This is followed by $$$t$$$ lines, three integers each $$$a$$$, $$$b$$$ and $$$c$$$ ($$$1 \le a, b, c \le 10^8$$$, $$$b \ne c$$$) — floor numbers described in the statement.

## Output Format
Output $$$t$$$ numbers, each of which is the answer to the corresponding test case. As an answer, output:

- $$$1$$$, if it is better to call the first elevator;
- $$$2$$$, if it is better to call the second one;
- $$$3$$$, if it doesn't matter which elevator to call (both elevators will arrive in the same time).

## Examples
```input
3
1 2 3
3 1 2
3 2 1
```
```output
1
3
2
```

## Note
In the first test case of the example, the first elevator is already on the floor of $$$1$$$.

In the second test case of the example, when called, the elevators would move as follows:

- At the time of the call, the first elevator is on the floor of $$$3$$$, and the second one is on the floor of $$$1$$$, but is already going to another floor;
- in $$$1$$$ second after the call, the first elevator would be on the floor $$$2$$$, the second one would also reach the floor $$$2$$$ and now can go to the floor $$$1$$$;
- in $$$2$$$ seconds, any elevator would reach the floor $$$1$$$.

In the third test case of the example, the first elevator will arrive in $$$2$$$ seconds, and the second in $$$1$$$.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You talked to Polycarp and asked him a question. You know that when he wants to answer "yes", he repeats Yes many times in a row.

Because of the noise, you only heard part of the answer — some substring of it. That is, if he answered YesYes, then you could hear esY, YesYes, sYes, e, but you couldn't Yess, YES or se.

Determine if it is true that the given string $$$s$$$ is a substring of YesYesYes... (Yes repeated many times in a row).

## Input Format
The first line of input data contains the singular $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the test.

Each test case is described by a single string of Latin letters $$$s$$$ ($$$1 \le |s| \le 50$$$) — the part of Polycarp's answer that you heard, where $$$|s|$$$ — is the length of the string $$$s$$$.

## Output Format
Output $$$t$$$ lines, each of which is the answer to the corresponding test case. As an answer, output "YES" if the specified string $$$s$$$ is a substring of the string YesYesYes...Yes (the number of words Yes is arbitrary), and "NO" otherwise.

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

## Examples
```input
12
YES
esYes
codeforces
es
se
YesY
esYesYesYesYesYesYe
seY
Yess
sY
o
Yes
```
```output
NO
YES
NO
YES
NO
YES
YES
NO
NO
YES
NO
YES
```

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Vlad came home and found out that someone had reconfigured the old thermostat to the temperature of $$$a$$$.

The thermostat can only be set to a temperature from $$$l$$$ to $$$r$$$ inclusive, the temperature cannot change by less than $$$x$$$. Formally, in one operation you can reconfigure the thermostat from temperature $$$a$$$ to temperature $$$b$$$ if $$$|a - b| \ge x$$$ and $$$l \le b \le r$$$.

You are given $$$l$$$, $$$r$$$, $$$x$$$, $$$a$$$ and $$$b$$$. Find the minimum number of operations required to get temperature $$$b$$$ from temperature $$$a$$$, or say that it is impossible.

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

The descriptions of the test cases follow.

The first line of each case contains three integers $$$l$$$, $$$r$$$ and $$$x$$$ ($$$-10^9 \le l \le r \le 10^9$$$, $$$1 \le x \le 10^9$$$) — range of temperature and minimum temperature change.

The second line of each case contains two integers $$$a$$$ and $$$b$$$ ($$$l \le a, b \le r$$$) — the initial and final temperatures.

## Output Format
Output $$$t$$$ numbers, each of which is the answer to the corresponding test case. If it is impossible to achieve the temperature $$$b$$$, output -1, otherwise output the minimum number of operations.

## Examples
```input
10
3 5 6
3 3
0 15 5
4 5
0 10 5
3 7
3 5 6
3 4
-10 10 11
-5 6
-3 3 4
1 0
-5 10 8
9 2
1 5 1
2 5
-1 4 3
0 2
-6 3 6
-1 -4
```
```output
0
2
3
-1
1
-1
3
1
3
-1
```

## Note
In the first example, the thermostat is already set up correctly.

In the second example, you can achieve the desired temperature as follows: $$$4 \rightarrow 10 \rightarrow 5$$$.

In the third example, you can achieve the desired temperature as follows: $$$3 \rightarrow 8 \rightarrow 2 \rightarrow 7$$$.

In the fourth test, it is impossible to make any operation.

Now solve the problem and return the code.