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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Consider a billiard table of rectangular size $$$n \times m$$$ with four pockets. Let's introduce a coordinate system with the origin at the lower left corner (see the picture).

There is one ball at the point $$$(x, y)$$$ currently. Max comes to the table and strikes the ball. The ball starts moving along a line that is parallel to one of the axes or that makes a $$$45^{\circ}$$$ angle with them. We will assume that:

1. the angles between the directions of the ball before and after a collision with a side are equal,
2. the ball moves indefinitely long, it only stops when it falls into a pocket,
3. the ball can be considered as a point, it falls into a pocket if and only if its coordinates coincide with one of the pockets,
4. initially the ball is not in a pocket.

Note that the ball can move along some side, in this case the ball will just fall into the pocket at the end of the side.

Your task is to determine whether the ball will fall into a pocket eventually, and if yes, which of the four pockets it will be.

## Input Format
The only line contains $$$6$$$ integers $$$n$$$, $$$m$$$, $$$x$$$, $$$y$$$, $$$v_x$$$, $$$v_y$$$ ($$$1 \leq n, m \leq 10^9$$$, $$$0 \leq x \leq n$$$; $$$0 \leq y \leq m$$$; $$$-1 \leq v_x, v_y \leq 1$$$; $$$(v_x, v_y) \neq (0, 0)$$$) — the width of the table, the length of the table, the $$$x$$$-coordinate of the initial position of the ball, the $$$y$$$-coordinate of the initial position of the ball, the $$$x$$$-component of its initial speed and the $$$y$$$-component of its initial speed, respectively. It is guaranteed that the ball is not initially in a pocket.

## Output Format
Print the coordinates of the pocket the ball will fall into, or $$$-1$$$ if the ball will move indefinitely.

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

## Note
The first sample:

The second sample:

In the third sample the ball will never change its $$$y$$$ coordinate, so the ball will never fall into a pocket.

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
Petr is a detective in Braginsk. Somebody stole a huge amount of money from a bank and Petr is to catch him. Somebody told Petr that some luxurious car moves along the roads without stopping.

Petr knows that it is the robbers who drive the car. The roads in Braginsk are one-directional and each of them connects two intersections. Petr wants to select one intersection such that if the robbers continue to drive the roads indefinitely, they will sooner or later come to that intersection. The initial position of the robbers is unknown. Find such an intersection that fits the requirements.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \le 10^5$$$, $$$2 \leq m \leq 5 \cdot 10^5$$$) — the number of intersections and the number of directed roads in Braginsk, respectively.

Each of the next $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — the start and finish of the $$$i$$$-th directed road. It is guaranteed that the robbers can move along the roads indefinitely.

## Output Format
Print a single integer $$$k$$$ — the intersection Petr needs to choose. If there are multiple answers, print any. If there are no such intersections, print $$$-1$$$.

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

## Note
In the first example the robbers can move, for example, along the following routes: $$$(1-2-3-1)$$$, $$$(3-4-5-3)$$$, $$$(1-2-3-4-5-3-1)$$$. We can show that if Petr chooses the $$$3$$$-rd intersection, he will eventually meet the robbers independently of their route.

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: 7.5 seconds
Memory limit: 45.0 MB

# Problem
Little Gerald and his coach Mike play an interesting game. At the beginning of the game there is a pile consisting of n candies and a pile consisting of m stones. Gerald and Mike move in turns, Mike goes first. During his move Mike checks how many candies and stones Gerald has eaten. Let Gerald eat a candies and b stones. Then Mike awards Gerald f(a, b) prize points. Gerald during his move either eats a candy from the pile of candies or a stone from the pile of stones. As Mike sees that Gerald has eaten everything apart one candy and one stone, he awards points for the last time and the game ends. Gerald is not allowed to eat all the candies, and he is not allowed to eat all the stones too. Tell Gerald how to play to get the largest possible number of points: it is required to find one of the possible optimal playing strategies for Gerald.

## Input Format
The first line contains three integers n, m, p (1 ≤ n, m ≤ 20000, 1 ≤ p ≤ 109). The second line contains n integers x0, x1, ..., xn - 1 (0 ≤ xi ≤ 20000). The third line contains m integers y0, y1, ..., ym - 1 (0 ≤ yi ≤ 20000). The value of f(a, b) is calculated as a remainder of the division of the sum xa + yb by number p.

## Output Format
Print on the first line the only number: the maximal number of points Gerald can earn. Print on the second line a sting consisting of n + m - 2 characters, each of which is either a "C" or "S", the i-th character should be "C" if Gerald's i-th move should be eating a candy and "S" if he should eat a stone.

## Examples
```input
2 2 10
0 0
0 1
```
```output
2
SC
```
-----
```input
3 3 10
0 2 0
0 0 2
```
```output
10
CSSC
```
-----
```input
3 3 2
0 1 1
1 1 0
```
```output
4
SCSC
```

## Note
In the first test if Gerald's first move is eating a stone, he will receive a point for it and if he eats a candy, he will get zero pints. In any way Gerald will get 0 points before his first move, and 1 after his second one. This, the maximum number of points Gerald can get equals to 2, and for that he should first eat a stone, then a candy.

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
John Smith knows that his son, Thomas Smith, is among the best students in his class and even in his school. After the students of the school took the exams in English, German, Math, and History, a table of results was formed.

There are $$$n$$$ students, each of them has a unique id (from $$$1$$$ to $$$n$$$). Thomas's id is $$$1$$$. Every student has four scores correspond to his or her English, German, Math, and History scores. The students are given in order of increasing of their ids.

In the table, the students will be sorted by decreasing the sum of their scores. So, a student with the largest sum will get the first place. If two or more students have the same sum, these students will be sorted by increasing their ids.

Please help John find out the rank of his son.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of students.

Each of the next $$$n$$$ lines contains four integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, and $$$d_i$$$ ($$$0\leq a_i, b_i, c_i, d_i\leq 100$$$) — the grades of the $$$i$$$-th student on English, German, Math, and History. The id of the $$$i$$$-th student is equal to $$$i$$$.

## Output Format
Print the rank of Thomas Smith. Thomas's id is $$$1$$$.

## Examples
```input
5
100 98 100 100
100 100 100 100
100 100 99 99
90 99 90 100
100 98 60 99
```
```output
2
```
-----
```input
6
100 80 90 99
60 60 60 60
90 60 100 60
60 100 60 80
100 100 0 100
0 0 0 0
```
```output
1
```

## Note
In the first sample, the students got total scores: $$$398$$$, $$$400$$$, $$$398$$$, $$$379$$$, and $$$357$$$. Among the $$$5$$$ students, Thomas and the third student have the second highest score, but Thomas has a smaller id, so his rank is $$$2$$$.

In the second sample, the students got total scores: $$$369$$$, $$$240$$$, $$$310$$$, $$$300$$$, $$$300$$$, and $$$0$$$. Among the $$$6$$$ students, Thomas got the highest score, so his rank is $$$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
Mrs. Smith is trying to contact her husband, John Smith, but she forgot the secret phone number!

The only thing Mrs. Smith remembered was that any permutation of $$$n$$$ can be a secret phone number. Only those permutations that minimize secret value might be the phone of her husband.

The sequence of $$$n$$$ integers is called a permutation if it contains all integers from $$$1$$$ to $$$n$$$ exactly once.

The secret value of a phone number is defined as the sum of the length of the longest increasing subsequence (LIS) and length of the longest decreasing subsequence (LDS).

A subsequence $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ where $$$1\leq i_1 < i_2 < \ldots < i_k\leq n$$$ is called increasing if $$$a_{i_1} < a_{i_2} < a_{i_3} < \ldots < a_{i_k}$$$. If $$$a_{i_1} > a_{i_2} > a_{i_3} > \ldots > a_{i_k}$$$, a subsequence is called decreasing. An increasing/decreasing subsequence is called longest if it has maximum length among all increasing/decreasing subsequences.

For example, if there is a permutation $$$[6, 4, 1, 7, 2, 3, 5]$$$, LIS of this permutation will be $$$[1, 2, 3, 5]$$$, so the length of LIS is equal to $$$4$$$. LDS can be $$$[6, 4, 1]$$$, $$$[6, 4, 2]$$$, or $$$[6, 4, 3]$$$, so the length of LDS is $$$3$$$.

Note, the lengths of LIS and LDS can be different.

So please help Mrs. Smith to find a permutation that gives a minimum sum of lengths of LIS and LDS.

## Input Format
The only line contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of permutation that you need to build.

## Output Format
Print a permutation that gives a minimum sum of lengths of LIS and LDS.

If there are multiple answers, print any.

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

## Note
In the first sample, you can build a permutation $$$[3, 4, 1, 2]$$$. LIS is $$$[3, 4]$$$ (or $$$[1, 2]$$$), so the length of LIS is equal to $$$2$$$. LDS can be ony of $$$[3, 1]$$$, $$$[4, 2]$$$, $$$[3, 2]$$$, or $$$[4, 1]$$$. The length of LDS is also equal to $$$2$$$. The sum is equal to $$$4$$$. Note that $$$[3, 4, 1, 2]$$$ is not the only permutation that is valid.

In the second sample, you can build a permutation $$$[2, 1]$$$. LIS is $$$[1]$$$ (or $$$[2]$$$), so the length of LIS is equal to $$$1$$$. LDS is $$$[2, 1]$$$, so the length of LDS is equal to $$$2$$$. The sum is equal to $$$3$$$. Note that permutation $$$[1, 2]$$$ is also valid.

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: 5.0 seconds
Memory limit: 16.0 MB

# Problem
Notice: unusual memory limit!

After the war, destroyed cities in the neutral zone were restored. And children went back to school.

The war changed the world, as well as education. In those hard days, a new math concept was created.

As we all know, logarithm function can be described as: $$$$$$ \log(p_1^{a_1}p_2^{a_2}...p_k^{a_2}) = a_1 \log p_1 + a_2 \log p_2 + ... + a_k \log p_k $$$$$$ Where $$$p_1^{a_1}p_2^{a_2}...p_k^{a_2}$$$ is the prime factorization of a integer. A problem is that the function uses itself in the definition. That is why it is hard to calculate.

So, the mathematicians from the neutral zone invented this: $$$$$$ \text{exlog}_f(p_1^{a_1}p_2^{a_2}...p_k^{a_2}) = a_1 f(p_1) + a_2 f(p_2) + ... + a_k f(p_k) $$$$$$

Notice that $$$\text{exlog}_f(1)$$$ is always equal to $$$0$$$.

This concept for any function $$$f$$$ was too hard for children. So teachers told them that $$$f$$$ can only be a polynomial of degree no more than $$$3$$$ in daily uses (i.e., $$$f(x) = Ax^3+Bx^2+Cx+D$$$).

"Class is over! Don't forget to do your homework!" Here it is: $$$$$$ \sum_{i=1}^n \text{exlog}_f(i) $$$$$$

Help children to do their homework. Since the value can be very big, you need to find the answer modulo $$$2^{32}$$$.

## Input Format
The only line contains five integers $$$n$$$, $$$A$$$, $$$B$$$, $$$C$$$, and $$$D$$$ ($$$1 \le n \le 3 \cdot 10^8$$$, $$$0 \le A,B,C,D \le 10^6$$$).

## Output Format
Print the answer modulo $$$2^{32}$$$.

## Examples
```input
12 0 0 1 0
```
```output
63
```
-----
```input
4 1 2 3 4
```
```output
136
```

## Note
In the first sample:

$$$\text{exlog}_f(1) = 0$$$

$$$\text{exlog}_f(2) = 2$$$

$$$\text{exlog}_f(3) = 3$$$

$$$\text{exlog}_f(4) = 2 + 2 = 4$$$

$$$\text{exlog}_f(5) = 5$$$

$$$\text{exlog}_f(6) = 2 + 3 = 5$$$

$$$\text{exlog}_f(7) = 7$$$

$$$\text{exlog}_f(8) = 2 + 2 + 2 = 6$$$

$$$\text{exlog}_f(9) = 3 + 3 = 6$$$

$$$\text{exlog}_f(10) = 2 + 5 = 7$$$

$$$\text{exlog}_f(11) = 11$$$

$$$\text{exlog}_f(12) = 2 + 2 + 3 = 7$$$

$$$ \sum_{i=1}^{12} \text{exlog}_f(i)=63 $$$

In the second sample:

$$$\text{exlog}_f(1) = 0$$$

$$$\text{exlog}_f(2) = (1 \times 2^3 + 2 \times 2^2 + 3 \times 2 + 4) = 26$$$

$$$\text{exlog}_f(3) = (1 \times 3^3 + 2 \times 3^2 + 3 \times 3 + 4) = 58$$$

$$$\text{exlog}_f(4) = 2 \times \text{exlog}_f(2) = 52$$$

$$$ \sum_{i=1}^4 \text{exlog}_f(i)=0+26+58+52=136 $$$

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: 256.0 MB

# Problem
Abendsen assigned a mission to Juliana. In this mission, Juliana has a rooted tree with $$$n$$$ vertices. Vertex number $$$1$$$ is the root of this tree. Each vertex can be either black or white. At first, all vertices are white. Juliana is asked to process $$$q$$$ queries. Each query is one of three types:

1. If vertex $$$v$$$ is white, mark it as black; otherwise, perform this operation on all direct sons of $$$v$$$ instead.
2. Mark all vertices in the subtree of $$$v$$$ (including $$$v$$$) as white.
3. Find the color of the $$$i$$$-th vertex.

An example of operation "1 1" (corresponds to the first example test). The vertices $$$1$$$ and $$$2$$$ are already black, so the operation goes to their sons instead.

Can you help Juliana to process all these queries?

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2\leq n\leq 10^5$$$, $$$1\leq q\leq 10^5$$$) — the number of vertices and the number of queries.

The second line contains $$$n-1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1\leq p_i<i$$$), where $$$p_i$$$ means that there is an edge between vertices $$$i$$$ and $$$p_i$$$.

Each of the next $$$q$$$ lines contains two integers $$$t_i$$$ and $$$v_i$$$ ($$$1\leq t_i\leq 3$$$, $$$1\leq v_i\leq n$$$) — the type of the $$$i$$$-th query and the vertex of the $$$i$$$-th query.

It is guaranteed that the given graph is a tree.

## Output Format
For each query of type $$$3$$$, print "black" if the vertex is black; otherwise, print "white".

## Examples
```input
8 10
1 2 1 2 5 4 5
1 2
3 2
3 1
1 1
1 1
3 5
3 7
3 4
2 2
3 5
```
```output
black
white
black
white
black
white
```
-----
```input
8 11
1 1 2 3 3 6 6
1 1
1 1
1 3
3 2
3 4
3 6
3 7
2 3
1 6
3 7
3 6
```
```output
black
white
black
white
white
black
```

## Note
The first example is shown on the picture below.

The second example is shown on the picture below.

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: 512.0 MB

# Problem
A group of $$$n$$$ dancers rehearses a performance for the closing ceremony. The dancers are arranged in a row, they've studied their dancing moves and can't change positions. For some of them, a white dancing suit is already bought, for some of them — a black one, and for the rest the suit will be bought in the future.

On the day when the suits were to be bought, the director was told that the participants of the olympiad will be happy if the colors of the suits on the scene will form a palindrome. A palindrome is a sequence that is the same when read from left to right and when read from right to left. The director liked the idea, and she wants to buy suits so that the color of the leftmost dancer's suit is the same as the color of the rightmost dancer's suit, the 2nd left is the same as 2nd right, and so on.

The director knows how many burls it costs to buy a white suit, and how many burls to buy a black suit. You need to find out whether it is possible to buy suits to form a palindrome, and if it's possible, what's the minimal cost of doing so. Remember that dancers can not change positions, and due to bureaucratic reasons it is not allowed to buy new suits for the dancers who already have suits, even if it reduces the overall spending.

## Input Format
The first line contains three integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$1 \leq n \leq 20$$$, $$$1 \leq a, b \leq 100$$$) — the number of dancers, the cost of a white suit, and the cost of a black suit.

The next line contains $$$n$$$ numbers $$$c_i$$$, $$$i$$$-th of which denotes the color of the suit of the $$$i$$$-th dancer. Number $$$0$$$ denotes the white color, $$$1$$$ — the black color, and $$$2$$$ denotes that a suit for this dancer is still to be bought.

## Output Format
If it is not possible to form a palindrome without swapping dancers and buying new suits for those who have one, then output -1. Otherwise, output the minimal price to get the desired visual effect.

## Examples
```input
5 100 1
0 1 2 1 2
```
```output
101
```
-----
```input
3 10 12
1 2 0
```
```output
-1
```
-----
```input
3 12 1
0 1 0
```
```output
0
```

## Note
In the first sample, the cheapest way to obtain palindromic colors is to buy a black suit for the third from left dancer and a white suit for the rightmost dancer.

In the second sample, the leftmost dancer's suit already differs from the rightmost dancer's suit so there is no way to obtain the desired coloring.

In the third sample, all suits are already bought and their colors form a palindrome.

Now solve the problem and return the code.