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

# Problem
There is a grid, consisting of $$$2$$$ rows and $$$n$$$ columns. Each cell of the grid is either free or blocked.

A free cell $$$y$$$ is reachable from a free cell $$$x$$$ if at least one of these conditions holds:

- $$$x$$$ and $$$y$$$ share a side;
- there exists a free cell $$$z$$$ such that $$$z$$$ is reachable from $$$x$$$ and $$$y$$$ is reachable from $$$z$$$.

A connected region is a set of free cells of the grid such that all cells in it are reachable from one another, but adding any other free cell to the set violates this rule.

For example, consider the following layout, where white cells are free, and dark grey cells are blocked:

There are $$$3$$$ regions in it, denoted with red, green and blue color respectively:

The given grid contains at most $$$1$$$ connected region. Your task is to calculate the number of free cells meeting the following constraint:

- if this cell is blocked, the number of connected regions becomes exactly $$$3$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of columns.

The $$$i$$$-th of the next two lines contains a description of the $$$i$$$-th row of the grid — the string $$$s_i$$$, consisting of $$$n$$$ characters. Each character is either . (denoting a free cell) or x (denoting a blocked cell).

Additional constraint on the input:

- the given grid contains at most $$$1$$$ connected region;
- the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the number of cells such that the number of connected regions becomes $$$3$$$ if this cell is blocked.

## Examples
```input
4
8
.......x
.x.xx...
2
..
..
3
xxx
xxx
9
..x.x.x.x
x.......x
```
```output
1
0
0
2
```

## Note
In the first test case, if the cell $$$(1, 3)$$$ is blocked, the number of connected regions becomes $$$3$$$ (as shown in the picture from the statement).

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
You are given a rooted tree, consisting of $$$n$$$ vertices. The vertices in the tree are numbered from $$$1$$$ to $$$n$$$, and the root is the vertex $$$1$$$. The value $$$a_i$$$ is written at the $$$i$$$-th vertex.

You can perform the following operation any number of times (possibly zero): choose a vertex $$$v$$$ which has at least one child; increase $$$a_v$$$ by $$$1$$$; and decrease $$$a_u$$$ by $$$1$$$ for all vertices $$$u$$$ that are in the subtree of $$$v$$$ (except $$$v$$$ itself). However, after each operation, the values on all vertices should be non-negative.

Your task is to calculate the maximum possible value written at the root using the aforementioned operation.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the initial values written at vertices.

The third line contains $$$n-1$$$ integers $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \le n$$$), where $$$p_i$$$ is the parent of the $$$i$$$-th vertex in the tree. Vertex $$$1$$$ is the root.

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

## Output Format
For each test case, print a single integer — the maximum possible value written at the root using the aforementioned operation.

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

## Note
In the first test case, the following sequence of operations is possible:

- perform the operation on $$$v=3$$$, then the values on the vertices will be $$$[0, 1, 1, 1]$$$;
- perform the operation on $$$v=1$$$, then the values on the vertices will be $$$[1, 0, 0, 0]$$$.

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
Monocarp is playing a computer game. He starts the game being level $$$1$$$. He is about to fight $$$n$$$ monsters, in order from $$$1$$$ to $$$n$$$. The level of the $$$i$$$-th monster is $$$a_i$$$.

For each monster in the given order, Monocarp's encounter goes as follows:

- if Monocarp's level is strictly higher than the monster's level, the monster flees (runs away);
- otherwise, Monocarp fights the monster.

After every $$$k$$$-th fight with a monster (fleeing monsters do not count), Monocarp's level increases by $$$1$$$. So, his level becomes $$$2$$$ after $$$k$$$ monsters he fights, $$$3$$$ after $$$2k$$$ monsters, $$$4$$$ after $$$3k$$$ monsters, and so on.

You need to process $$$q$$$ queries of the following form:

- $$$i~x$$$: will Monocarp fight the $$$i$$$-th monster (or will this monster flee) if the parameter $$$k$$$ is equal to $$$x$$$?

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — the levels of the monsters.

In the $$$j$$$-th of the following $$$q$$$ lines, two integers $$$i$$$ and $$$x$$$ ($$$1 \le i, x \le n$$$) — the index of the monster and the number of fights required for a level up in the $$$j$$$-th query.

## Output Format
For each query, output "YES", if Monocarp will fight the $$$i$$$-th monster in this query, and "NO", if the $$$i$$$-th monster flees.

## Examples
```input
4 16
2 1 2 1
1 1
2 1
3 1
4 1
1 2
2 2
3 2
4 2
1 3
2 3
3 3
4 3
1 4
2 4
3 4
4 4
```
```output
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
```
-----
```input
7 15
1 1 2 1 1 1 1
5 3
2 2
2 2
1 6
5 1
5 5
7 7
3 5
7 4
4 3
2 5
1 2
5 6
4 1
6 1
```
```output
NO
YES
YES
YES
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
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 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: 512.0 MB

# Problem
You have $$$n$$$ chips, and you are going to place all of them in one of $$$x$$$ points, numbered from $$$1$$$ to $$$x$$$. There can be multiple chips in each point.

After placing the chips, you can perform the following four operations (in any order, any number of times):

- choose a chip in point $$$i \ge 3$$$, remove it and place two chips: one in $$$i-1$$$, one in $$$i-2$$$;
- choose two chips in adjacent points $$$i$$$ and $$$i+1$$$, remove them and place a new chip in $$$i+2$$$;
- choose a chip in point $$$1$$$ and move it to $$$2$$$;
- choose a chip in point $$$2$$$ and move it to $$$1$$$.

Note that the coordinates of the chips you place during the operations cannot be less than $$$1$$$, but can be greater than $$$x$$$.

Denote the cost of chip placement as the minimum number of chips which can be present on the line after you perform these operations, starting from the placement you've chosen.

For example, the cost of placing two chips in points $$$3$$$ and one chip in point $$$5$$$ is $$$2$$$, because you can reduce the number of chips to $$$2$$$ as follows:

- choose a chip in point $$$3$$$, remove it, place a chip in $$$1$$$ and another chip in $$$2$$$;
- choose the chips in points $$$2$$$ and $$$3$$$, remove them and place a chip in $$$4$$$;
- choose the chips in points $$$4$$$ and $$$5$$$, remove them and place a chip in $$$6$$$.

You are given three integers $$$n$$$, $$$x$$$ and $$$m$$$. Calculate the number of placements of exactly $$$n$$$ chips in points from $$$1$$$ to $$$x$$$ having cost equal to $$$m$$$, and print it modulo $$$998244353$$$. Two placements are considered different if the number of chips in some point differs between these placements.

## Input Format
The only line contains three integers $$$n$$$, $$$x$$$ and $$$m$$$ ($$$1 \le m \le n \le 1000$$$; $$$2 \le x \le 10$$$).

## Output Format
Print one integer — the number of placements with cost equal to $$$m$$$, taken modulo $$$998244353$$$.

## Examples
```input
2 3 1
```
```output
5
```
-----
```input
42 10 5
```
```output
902673363
```
-----
```input
1000 10 8
```
```output
187821763
```

## Note
In the first example, there are five ways to place $$$2$$$ chips in points from $$$1$$$ to $$$3$$$ so that the cost is $$$1$$$:

- $$$(1, 1)$$$;
- $$$(1, 2)$$$;
- $$$(1, 3)$$$;
- $$$(2, 2)$$$;
- $$$(2, 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: 0.5 seconds
Memory limit: 256.0 MB

# Problem
The Little Elephant loves sortings.

He has an array a consisting of n integers. Let's number the array elements from 1 to n, then the i-th element will be denoted as ai. The Little Elephant can make one move to choose an arbitrary pair of integers l and r (1 ≤ l ≤ r ≤ n) and increase ai by 1 for all i such that l ≤ i ≤ r.

Help the Little Elephant find the minimum number of moves he needs to convert array a to an arbitrary array sorted in the non-decreasing order. Array a, consisting of n elements, is sorted in the non-decreasing order if for any i (1 ≤ i < n) ai ≤ ai + 1 holds.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 105) — the size of array a. The next line contains n integers, separated by single spaces — array a (1 ≤ ai ≤ 109). The array elements are listed in the line in the order of their index's increasing.

## Output Format
In a single line print a single integer — the answer to the problem.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

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

## Note
In the first sample the array is already sorted in the non-decreasing order, so the answer is 0.

In the second sample you need to perform two operations: first increase numbers from second to third (after that the array will be: [3, 3, 2]), and second increase only the last element (the array will be: [3, 3, 3]).

In the third sample you should make at least 6 steps. The possible sequence of the operations is: (2; 3), (2; 3), (2; 3), (3; 3), (3; 3), (3; 3). After that the array converts to [7, 7, 7, 47].

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
Polycarpus plays with red and blue marbles. He put n marbles from the left to the right in a row. As it turned out, the marbles form a zebroid.

A non-empty sequence of red and blue marbles is a zebroid, if the colors of the marbles in this sequence alternate. For example, sequences (red; blue; red) and (blue) are zebroids and sequence (red; red) is not a zebroid.

Now Polycarpus wonders, how many ways there are to pick a zebroid subsequence from this sequence. Help him solve the problem, find the number of ways modulo 1000000007 (109 + 7).

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 106) — the number of marbles in Polycarpus's sequence.

## Output Format
Print a single number — the answer to the problem modulo 1000000007 (109 + 7).

## Examples
```input
3
```
```output
6
```
-----
```input
4
```
```output
11
```

## Note
Let's consider the first test sample. Let's assume that Polycarpus initially had sequence (red; blue; red), so there are six ways to pick a zebroid:

- pick the first marble;
- pick the second marble;
- pick the third marble;
- pick the first and second marbles;
- pick the second and third marbles;
- pick the first, second and third marbles.

It can be proven that if Polycarpus picks (blue; red; blue) as the initial sequence, the number of ways won't 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
Flatland is inhabited by pixels of three colors: red, green and blue. We know that if two pixels of different colors meet in a violent fight, only one of them survives the fight (that is, the total number of pixels decreases by one). Besides, if pixels of colors x and y (x ≠ y) meet in a violent fight, then the pixel that survives the fight immediately changes its color to z (z ≠ x; z ≠ y). Pixels of the same color are friends, so they don't fight.

The King of Flatland knows that his land will be peaceful and prosperous when the pixels are of the same color. For each of the three colors you know the number of pixels of this color that inhabit Flatland. Help the king and determine whether fights can bring peace and prosperity to the country and if it is possible, find the minimum number of fights needed to make the land peaceful and prosperous.

## Input Format
The first line contains three space-separated integers a, b and c (0 ≤ a, b, c ≤ 231; a + b + c > 0) — the number of red, green and blue pixels, correspondingly.

## Output Format
Print a single number — the minimum number of pixel fights before the country becomes peaceful and prosperous. If making the country peaceful and prosperous is impossible, print -1.

## Examples
```input
1 1 1
```
```output
1
```
-----
```input
3 1 0
```
```output
3
```

## Note
In the first test sample the country needs only one fight to achieve peace and prosperity. Besides, it can be any fight whatsoever. For example, let's assume that the green and the blue pixels fight, then the surviving pixel will be red. As a result, after the fight there are two red pixels. There won't be other pixels.

In the second sample the following sequence of fights is possible: red and blue, green and red, red and blue. As a result, after all fights there is one green pixel left.

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

# Problem
Vasya went for a walk in the park. The park has n glades, numbered from 1 to n. There are m trails between the glades. The trails are numbered from 1 to m, where the i-th trail connects glades xi and yi. The numbers of the connected glades may be the same (xi = yi), which means that a trail connects a glade to itself. Also, two glades may have several non-intersecting trails between them.

Vasya is on glade 1, he wants to walk on all trails of the park exactly once, so that he can eventually return to glade 1. Unfortunately, Vasya does not know whether this walk is possible or not. Help Vasya, determine whether the walk is possible or not. If such walk is impossible, find the minimum number of trails the authorities need to add to the park in order to make the described walk possible.

Vasya can shift from one trail to another one only on glades. He can move on the trails in both directions. If Vasya started going on the trail that connects glades a and b, from glade a, then he must finish this trail on glade b.

## Input Format
The first line contains two integers n and m (1 ≤ n ≤ 106; 0 ≤ m ≤ 106) — the number of glades in the park and the number of trails in the park, respectively. Next m lines specify the trails. The i-th line specifies the i-th trail as two space-separated numbers, xi, yi (1 ≤ xi, yi ≤ n) — the numbers of the glades connected by this trail.

## Output Format
Print the single integer — the answer to the problem. If Vasya's walk is possible without adding extra trails, print 0, otherwise print the minimum number of trails the authorities need to add to the park in order to make Vasya's walk possible.

## Examples
```input
3 3
1 2
2 3
3 1
```
```output
0
```
-----
```input
2 5
1 1
1 2
1 2
2 2
1 2
```
```output
1
```

## Note
In the first test case the described walk is possible without building extra trails. For example, let's first go on the first trail, then on the second one, and finally on the third one.

In the second test case the described walk is impossible without adding extra trails. To make the walk possible, it is enough to add one trail, for example, between glades number one and two.

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

# Problem
Jabber ID on the national Berland service «Babber» has a form <username>@<hostname>[/resource], where

- <username> — is a sequence of Latin letters (lowercase or uppercase), digits or underscores characters «_», the length of <username> is between 1 and 16, inclusive.
- <hostname> — is a sequence of word separated by periods (characters «.»), where each word should contain only characters allowed for <username>, the length of each word is between 1 and 16, inclusive. The length of <hostname> is between 1 and 32, inclusive.
- <resource> — is a sequence of Latin letters (lowercase or uppercase), digits or underscores characters «_», the length of <resource> is between 1 and 16, inclusive.

The content of square brackets is optional — it can be present or can be absent.

There are the samples of correct Jabber IDs: [email protected], [email protected]/contest.

Your task is to write program which checks if given string is a correct Jabber ID.

## Input Format
The input contains of a single line. The line has the length between 1 and 100 characters, inclusive. Each characters has ASCII-code between 33 and 127, inclusive.

## Output Format
Print YES or NO.

## Examples
```input
[email protected]
```
```output
YES
```
-----
```input
[email protected]
/contest.icpc/12
```
```output
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 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 given two set of points. The first set is determined by the equation A1x + B1y + C1 = 0, and the second one is determined by the equation A2x + B2y + C2 = 0.

Write the program which finds the number of points in the intersection of two given sets.

## Input Format
The first line of the input contains three integer numbers A1, B1, C1 separated by space. The second line contains three integer numbers A2, B2, C2 separated by space. All the numbers are between -100 and 100, inclusive.

## Output Format
Print the number of points in the intersection or -1 if there are infinite number of points.

## Examples
```input
1 1 0
2 2 0
```
```output
-1
```
-----
```input
1 1 0
2 -2 0
```
```output
1
```

Now solve the problem and return the code.