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.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 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
The famous store "Second Food" sells groceries only two days a month. And the prices in each of days differ. You wanted to buy $$$n$$$ kilos of potatoes for a month. You know that on the first day of the month $$$1$$$ kilo of potatoes costs $$$a$$$ coins, and on the second day $$$b$$$ coins. In "Second Food" you can buy any integer kilograms of potatoes.

Fortunately, "Second Food" has announced a promotion for potatoes, which is valid only on the first day of the month — for each $$$m$$$ kilos of potatoes you buy, you get $$$1$$$ kilo as a gift! In other words, you can get $$$m + 1$$$ kilograms by paying for $$$m$$$ kilograms.

Find the minimum number of coins that you have to spend to buy at least $$$n$$$ kilos of potatoes.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10\,000$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$a$$$ and $$$b$$$ $$$(1 \leq a, b \leq 10^9)$$$ — the prices of $$$1$$$ kilo of potatoes on the first and second days, respectively.

The second line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 10^9)$$$ — the required amount of potatoes to buy and the amount of potatoes to use the promotion.

## Output Format
For each test case print one integer — the minimum number of coins that you have to pay to buy at least $$$n$$$ kilos of potatoes.

## Examples
```input
5
5 4
3 1
5 4
3 2
3 4
3 5
20 15
10 2
1000000000 900000000
1000000000 8
```
```output
9
10
9
135
888888888900000000
```

## Note
In the first test case, on the first day you buy $$$1$$$ kilo and get $$$1$$$ more for a promotion. On the second day, you can buy $$$1$$$ kilo of potatoes. Thus, you will spend $$$5+4=9$$$ coins in total.

In the second test case, on the first day you buy $$$2$$$ kilo and get another $$$1$$$ more for a promotion. This way you will spend $$$2 \cdot 5 = 10$$$ coins.

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
For his birthday recently Fedya was given an array $$$a$$$ of $$$n$$$ integers arranged in a circle, For each pair of neighboring numbers ($$$a_1$$$ and $$$a_2$$$, $$$a_2$$$ and $$$a_3$$$, $$$\ldots$$$, $$$a_{n - 1}$$$ and $$$a_n$$$, $$$a_n$$$ and $$$a_1$$$) the absolute difference between them is equal to $$$1$$$.

Let's call a local maximum an element, which is greater than both of its neighboring elements. Also call a local minimum an element, which is less than both of its neighboring elements. Note, that elements $$$a_1$$$ and $$$a_n$$$ are neighboring elements.

Unfortunately, Fedya lost an array, but he remembered in it the sum of local maximums $$$x$$$ and the sum of local minimums $$$y$$$.

Given $$$x$$$ and $$$y$$$, help Fedya find any matching array of minimum length.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.

Each line of each test case contain two integers $$$x$$$ and $$$y$$$ ($$$-10^{9} \le y < x \le 10^{9}$$$) — the sum of local maximums and the sum of local minimums, respectively.

## Output Format
For each test case, in the first line print one integer $$$n$$$ — the minimum length of matching arrays.

In the second line print $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^{9} \leqslant a_i \leqslant 10^{9}$$$) — the array elements such that the the absolute difference between each pair of neighboring is equal to $$$1$$$.

If there are multiple solutions, print any of them.

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

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

## Note
In the first test case, the local maximums are the numbers at $$$3, 7$$$ and $$$10$$$ positions, and the local minimums are the numbers at $$$1, 6$$$ and $$$8$$$ positions. $$$x = a_3 + a_7 + a_{10} = 2 + 0 + 1 = 3$$$, $$$y = a_1 + a_6 + a_8 = 0 + (-1) + (-1) = -2$$$.

In the second test case, the local maximums are the numbers at $$$2$$$ and $$$10$$$ positions, and the local minimums are the numbers at $$$1$$$ and $$$3$$$ positions. $$$x = a_2 + a_{10} = -1 + 5 = 4$$$, $$$y = a_1 + a_3 = -2 + (-2) = -4$$$.

In the third test case, the local maximums are the numbers at $$$1$$$ and $$$5$$$ positions, and the local minimums are the numbers at $$$3$$$ and $$$6$$$ positions.

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
In winter, the inhabitants of the Moscow Zoo are very bored, in particular, it concerns gorillas. You decided to entertain them and brought a permutation $$$p$$$ of length $$$n$$$ to the zoo.

A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in any order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ occurs twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$, but $$$4$$$ is present in the array).

The gorillas had their own permutation $$$q$$$ of length $$$n$$$. They suggested that you count the number of pairs of integers $$$l, r$$$ ($$$1 \le l \le r \le n$$$) such that $$$\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])=\operatorname{MEX}([q_l, q_{l+1}, \ldots, q_r])$$$.

The $$$\operatorname{MEX}$$$ of the sequence is the minimum integer positive number missing from this sequence. For example, $$$\operatorname{MEX}([1, 3]) = 2$$$, $$$\operatorname{MEX}([5]) = 1$$$, $$$\operatorname{MEX}([3, 1, 2, 6]) = 4$$$.

You do not want to risk your health, so you will not dare to refuse the gorillas.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the permutations length.

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

The third line contains $$$n$$$ integers $$$q_1, q_2, \ldots, q_n$$$ ($$$1 \le q_i \le n$$$) — the elements of the permutation $$$q$$$.

## Output Format
Print a single integer — the number of suitable pairs $$$l$$$ and $$$r$$$.

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

## Note
In the first example, two segments are correct – $$$[1, 3]$$$ with $$$\operatorname{MEX}$$$ equal to $$$4$$$ in both arrays and $$$[3, 3]$$$ with $$$\operatorname{MEX}$$$ equal to $$$1$$$ in both of arrays.

In the second example, for example, the segment $$$[1, 4]$$$ is correct, and the segment $$$[6, 7]$$$ isn't correct, because $$$\operatorname{MEX}(5, 4) \neq \operatorname{MEX}(1, 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There is a rectangular maze of size $$$n\times m$$$. Denote $$$(r,c)$$$ as the cell on the $$$r$$$-th row from the top and the $$$c$$$-th column from the left. Two cells are adjacent if they share an edge. A path is a sequence of adjacent empty cells.

Each cell is initially empty. Li Hua can choose some cells (except $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$) and place an obstacle in each of them. He wants to know the minimum number of obstacles needed to be placed so that there isn't a path from $$$(x_1, y_1)$$$ to $$$(x_2, y_2)$$$.

Suppose you were Li Hua, please solve this problem.

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

The first line of each test case contains two integers $$$n,m$$$ ($$$4\le n,m\le 10^9$$$) — the size of the maze.

The second line of each test case contains four integers $$$x_1,y_1,x_2,y_2$$$ ($$$1\le x_1,x_2\le n, 1\le y_1,y_2\le m$$$) — the coordinates of the start and the end.

It is guaranteed that $$$|x_1-x_2|+|y_1-y_2|\ge 2$$$.

## Output Format
For each test case print the minimum number of obstacles you need to put on the field so that there is no path from $$$(x_1, y_1)$$$ to $$$(x_2, y_2)$$$.

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

## Note
In test case 1, you can put obstacles on $$$(1,3), (2,3), (3,2), (4,2)$$$. Then the path from $$$(2,2)$$$ to $$$(3,3)$$$ will not exist.

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
Li Hua wants to solve a problem about $$$\varphi$$$ — Euler's totient function. Please recall that $$$\varphi(x)=\sum\limits_{i=1}^x[\gcd(i,x)=1]$$$.$$$^{\dagger,\ddagger}$$$

He has a sequence $$$a_1,a_2,\cdots,a_n$$$ and he wants to perform $$$m$$$ operations:

- "1 $$$l$$$ $$$r$$$" ($$$1\le l\le r\le n$$$) — for each $$$x\in[l,r]$$$, change $$$a_x$$$ into $$$\varphi(a_x)$$$.
- "2 $$$l$$$ $$$r$$$" ($$$1\le l\le r\le n$$$) — find out the minimum changes needed to make sure $$$a_l=a_{l+1}=\cdots=a_r$$$. In each change, he chooses one $$$x\in[l,r]$$$, change $$$a_x$$$ into $$$\varphi(a_x)$$$. Each operation of this type is independent, which means the array doesn't actually change.

Suppose you were Li Hua, please solve this problem.

$$$^\dagger$$$ $$$\gcd(x,y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

$$$^\ddagger$$$ The notation $$$[\textrm{cond}]$$$ equals $$$1$$$ if the condition $$$\textrm{cond}$$$ is true, and $$$0$$$ otherwise.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 10^{5}$$$) — the number of elements in the array and the number of operations to process, respectively.

The second line contains $$$n$$$ integers $$$a_{1},a_{2},\cdots ,a_{n}$$$ ($$$1\le a_{i}\le 5\cdot 10^{6}$$$) — the elements of the array.

Next $$$m$$$ lines, each line contains three integers $$$t_{i},l_{i},r_{i}$$$ ($$$t_i\in\{1,2\},1\le l_i\le r_i\le n$$$) — the $$$i$$$-th operation.

## Output Format
For each "2 $$$l$$$ $$$r$$$", output the answer in an separate line.

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

## Note
Denote $$$\varphi^k(x)=\begin{cases}x,&k=0\\\varphi(\varphi^{k-1}(x)),&k > 0\end{cases}$$$.

At first, $$$a=[8,1,6,3,7]$$$.

To make sure $$$a_1=a_2=a_3=a_4=a_5$$$, we can change $$$a$$$ to $$$a'=[\varphi^3(8),\varphi^0(1),\varphi^2(6),\varphi^2(3),\varphi^3(7)]=[1,1,1,1,1]$$$, using $$$3+0+2+2+3=10$$$ changes.

To make sure $$$a_3=a_4$$$, we can change $$$a$$$ to $$$a'=[\varphi^0(8),\varphi^0(1),\varphi^1(6),\varphi^1(3),\varphi^0(7)]=[8,1,2,2,7]$$$, using $$$0+0+1+1+0=2$$$ changes.

After "1 $$$1$$$ $$$3$$$", $$$a$$$ is changed to $$$a=[\varphi^1(8),\varphi^1(1),\varphi^1(6),\varphi^0(3),\varphi^0(7)]=[4,1,2,3,7]$$$.

To make sure $$$a_3=a_4$$$, we can change $$$a$$$ to $$$a'=[\varphi^0(4),\varphi^0(1),\varphi^0(2),\varphi^1(3),\varphi^0(7)]=[4,1,2,2,7]$$$, using $$$0+0+0+1+0=1$$$ change.

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
Li Hua has a tree of $$$n$$$ vertices and $$$n-1$$$ edges. The vertices are numbered from $$$1$$$ to $$$n$$$.

A pair of vertices $$$(u,v)$$$ ($$$u < v$$$) is considered cute if exactly one of the following two statements is true:

- $$$u$$$ is the vertex with the minimum index among all vertices on the path $$$(u,v)$$$.
- $$$v$$$ is the vertex with the maximum index among all vertices on the path $$$(u,v)$$$.

There will be $$$m$$$ operations. In each operation, he decides an integer $$$k_j$$$, then inserts a vertex numbered $$$n+j$$$ to the tree, connecting with the vertex numbered $$$k_j$$$.

He wants to calculate the number of cute pairs before operations and after each operation.

Suppose you were Li Hua, please solve this problem.

## Input Format
The first line contains the single integer $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — the number of vertices in the tree.

Next $$$n-1$$$ lines contain the edges of the tree. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1\le u_i,v_i\le n$$$; $$$u_i\ne v_i$$$) — the corresponding edge. The given edges form a tree.

The next line contains the single integer $$$m$$$ ($$$1\le m\le 2\cdot 10^5$$$) — the number of operations.

Next $$$m$$$ lines contain operations — one operation per line. The $$$j$$$-th operation contains one integer $$$k_j$$$ ($$$1\le k_j < n+j$$$) — a vertex.

## Output Format
Print $$$m+1$$$ integers — the number of cute pairs before operations and after each operation.

## Examples
```input
7
2 1
1 3
1 4
4 6
4 7
6 5
2
5
6
```
```output
11
15
19
```

## Note
The initial tree is shown in the following picture:

There are $$$11$$$ cute pairs — $$$(1,5),(2,3),(2,4),(2,6),(2,7),(3,4),(3,6),(3,7),(4,5),(5,7),(6,7)$$$.

Similarly, we can count the cute pairs after each operation and the result is $$$15$$$ and $$$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 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
In this problem, unlike problem A, you need to look for unluckiest number, not the luckiest one.

Note that the constraints of this problem differ from such in problem A.

Olympus City recently launched the production of personal starships. Now everyone on Mars can buy one and fly to other planets inexpensively.

Each starship has a number —some positive integer $$$x$$$. Let's define the luckiness of a number $$$x$$$ as the difference between the largest and smallest digits of that number. For example, $$$142857$$$ has $$$8$$$ as its largest digit and $$$1$$$ as its smallest digit, so its luckiness is $$$8-1=7$$$. And the number $$$111$$$ has all digits equal to $$$1$$$, so its luckiness is zero.

Hateehc is a famous Martian blogger who often flies to different corners of the solar system. To release interesting videos even faster, he decided to buy himself a starship. When he came to the store, he saw starships with numbers from $$$l$$$ to $$$r$$$ inclusively. While in the store, Hateehc wanted to find a starship with the unluckiest number.

Since there are a lot of starships in the store, and Hateehc can't program, you have to help the blogger and write a program that answers his question.

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

Each of the following $$$t$$$ lines contains a description of the test case. The description consists of two integers $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$) — the largest and smallest numbers of the starships in the store.

## Output Format
Print $$$t$$$ lines, one line for each test case, containing the unluckiest starship number in the store.

If there are several ways to choose the unluckiest number, output any of them.

## Examples
```input
5
59 63
42 49
48 53
90 90
1 100
```
```output
63
44
53
90
1
```

## Note
Let's look at two test examples:

- the luckiness of the number $$$59$$$ is $$$9 - 5 = 4$$$;
- the luckiness of $$$60$$$ equals $$$6 - 0 = 6$$$;
- the luckiness of $$$61$$$ equals $$$6 - 1 = 5$$$;
- the luckiness of $$$62$$$ equals $$$6 - 2 = 4$$$;
- the luckiness of $$$63$$$ is $$$6 - 3 = 3$$$.

In the fifth test case, the unluckiest numbers are $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$7$$$, $$$8$$$, $$$9$$$, $$$11$$$, $$$22$$$, $$$33$$$, $$$44$$$, $$$55$$$, $$$66$$$, $$$77$$$, $$$88$$$, $$$99$$$, so you are allowed to choose any of them.

Now solve the problem and return the code.