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
You are given four integer values $$$a$$$, $$$b$$$, $$$c$$$ and $$$m$$$.

Check if there exists a string that contains:

- $$$a$$$ letters 'A';
- $$$b$$$ letters 'B';
- $$$c$$$ letters 'C';
- no other letters;
- exactly $$$m$$$ pairs of adjacent equal letters (exactly $$$m$$$ such positions $$$i$$$ that the $$$i$$$-th letter is equal to the $$$(i+1)$$$-th one).

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

Each of the next $$$t$$$ lines contains the description of the testcase — four integers $$$a$$$, $$$b$$$, $$$c$$$ and $$$m$$$ ($$$1 \le a, b, c \le 10^8$$$; $$$0 \le m \le 10^8$$$).

## Output Format
For each testcase print "YES" if there exists a string that satisfies all the requirements. Print "NO" if there are no such strings.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).

## Examples
```input
3
2 2 1 0
1 1 1 1
1 2 3 2
```
```output
YES
NO
YES
```

## Note
In the first testcase strings "ABCAB" or "BCABA" satisfy the requirements. There exist other possible strings.

In the second testcase there's no way to put adjacent equal letters if there's no letter that appears at least twice.

In the third testcase string "CABBCC" satisfies the requirements. There exist other possible strings.

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
Ivan is playing yet another roguelike computer game. He controls a single hero in the game. The hero has $$$n$$$ equipment slots. There is a list of $$$c_i$$$ items for the $$$i$$$-th slot, the $$$j$$$-th of them increases the hero strength by $$$a_{i,j}$$$. The items for each slot are pairwise distinct and are listed in the increasing order of their strength increase. So, $$$a_{i,1} < a_{i,2} < \dots < a_{i,c_i}$$$.

For each slot Ivan chooses exactly one item. Let the chosen item for the $$$i$$$-th slot be the $$$b_i$$$-th item in the corresponding list. The sequence of choices $$$[b_1, b_2, \dots, b_n]$$$ is called a build.

The strength of a build is the sum of the strength increases of the items in it. Some builds are banned from the game. There is a list of $$$m$$$ pairwise distinct banned builds. It's guaranteed that there's at least one build that's not banned.

What is the build with the maximum strength that is not banned from the game? If there are multiple builds with maximum strength, print any of them.

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

The $$$i$$$-th of the next $$$n$$$ lines contains the description of the items for the $$$i$$$-th slot. First, one integer $$$c_i$$$ ($$$1 \le c_i \le 2 \cdot 10^5$$$) — the number of items for the $$$i$$$-th slot. Then $$$c_i$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,c_i}$$$ ($$$1 \le a_{i,1} < a_{i,2} < \dots < a_{i,c_i} \le 10^8$$$).

The sum of $$$c_i$$$ doesn't exceed $$$2 \cdot 10^5$$$.

The next line contains a single integer $$$m$$$ ($$$0 \le m \le 10^5$$$) — the number of banned builds.

Each of the next $$$m$$$ lines contains a description of a banned build — a sequence of $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le c_i$$$).

The builds are pairwise distinct, and there's at least one build that's not banned.

## Output Format
Print the build with the maximum strength that is not banned from the game. If there are multiple builds with maximum strength, print any of them.

## Examples
```input
3
3 1 2 3
2 1 5
3 2 4 6
2
3 2 3
3 2 2
```
```output
2 2 3
```
-----
```input
3
3 1 2 3
2 1 5
3 2 4 6
2
3 2 3
2 2 3
```
```output
1 2 3
```
-----
```input
3
3 1 2 3
2 1 5
3 2 4 6
2
3 2 3
2 2 3
```
```output
3 2 2
```
-----
```input
4
1 10
1 4
1 7
1 3
0
```
```output
1 1 1 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A matrix of size $$$n \times m$$$, such that each cell of it contains either $$$0$$$ or $$$1$$$, is considered beautiful if the sum in every contiguous submatrix of size $$$2 \times 2$$$ is exactly $$$2$$$, i. e. every "square" of size $$$2 \times 2$$$ contains exactly two $$$1$$$'s and exactly two $$$0$$$'s.

You are given a matrix of size $$$n \times m$$$. Initially each cell of this matrix is empty. Let's denote the cell on the intersection of the $$$x$$$-th row and the $$$y$$$-th column as $$$(x, y)$$$. You have to process the queries of three types:

- $$$x$$$ $$$y$$$ $$$-1$$$ — clear the cell $$$(x, y)$$$, if there was a number in it;
- $$$x$$$ $$$y$$$ $$$0$$$ — write the number $$$0$$$ in the cell $$$(x, y)$$$, overwriting the number that was there previously (if any);
- $$$x$$$ $$$y$$$ $$$1$$$ — write the number $$$1$$$ in the cell $$$(x, y)$$$, overwriting the number that was there previously (if any).

After each query, print the number of ways to fill the empty cells of the matrix so that the resulting matrix is beautiful. Since the answers can be large, print them modulo $$$998244353$$$.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n, m \le 10^6$$$; $$$1 \le k \le 3 \cdot 10^5$$$) — the number of rows in the matrix, the number of columns, and the number of queries, respectively.

Then $$$k$$$ lines follow, the $$$i$$$-th of them contains three integers $$$x_i$$$, $$$y_i$$$, $$$t_i$$$ ($$$1 \le x_i \le n$$$; $$$1 \le y_i \le m$$$; $$$-1 \le t_i \le 1$$$) — the parameters for the $$$i$$$-th query.

## Output Format
For each query, print one integer — the number of ways to fill the empty cells of the matrix after the respective query, taken modulo $$$998244353$$$.

## Examples
```input
2 2 7
1 1 1
1 2 1
2 1 1
1 1 0
1 2 -1
2 1 -1
1 1 -1
```
```output
3
1
0
1
2
3
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: 7.0 seconds
Memory limit: 512.0 MB

# Problem
A subarray of array $$$a$$$ from index $$$l$$$ to the index $$$r$$$ is the array $$$[a_l, a_{l+1}, \dots, a_{r}]$$$. The number of occurrences of the array $$$b$$$ in the array $$$a$$$ is the number of subarrays of $$$a$$$ such that they are equal to $$$b$$$.

You are given $$$n$$$ arrays $$$A_1, A_2, \dots, A_n$$$; the elements of these arrays are integers from $$$1$$$ to $$$k$$$. You have to build an array $$$a$$$ consisting of $$$m$$$ integers from $$$1$$$ to $$$k$$$ in such a way that, for every given subarray $$$A_i$$$, the number of occurrences of $$$A_i$$$ in the array $$$a$$$ is not less than the number of occurrences of each non-empty subarray of $$$A_i$$$ in $$$a$$$. Note that if $$$A_i$$$ doesn't occur in $$$a$$$, and no subarray of $$$A_i$$$ occurs in $$$a$$$, this condition is still met for $$$A_i$$$.

Your task is to calculate the number of different arrays $$$a$$$ you can build, and print it modulo $$$998244353$$$.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n, m, k \le 3 \cdot 10^5$$$) — the number of the given arrays, the desired length of the array $$$a$$$, and the upper bound on the values in the arrays.

Then $$$n$$$ lines follow. The $$$i$$$-th line represents the array $$$A_i$$$. The first integer in the $$$i$$$-th line is $$$c_i$$$ ($$$1 \le c_i \le m$$$) — the number of elements in $$$A_i$$$; then, $$$c_i$$$ integers from $$$1$$$ to $$$k$$$ follow — the elements of the array $$$A_i$$$.

Additional constraint on the input: $$$\sum\limits_{i=1}^n c_i \le 3 \cdot 10^5$$$; i. e., the number of elements in the given arrays in total does not exceed $$$3 \cdot 10^5$$$.

## Output Format
Print one integer — the number of different arrays $$$a$$$ you can build, taken modulo $$$998244353$$$.

## Examples
```input
2 4 3
2 1 2
1 3
```
```output
5
```
-----
```input
2 4 3
2 1 2
3 3 2 1
```
```output
0
```
-----
```input
1 42 1337
2 13 31
```
```output
721234447
```

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
"Contestant who earns a score equal to or greater than the k-th place finisher's score will advance to the next round, as long as the contestant earns a positive score..." — an excerpt from contest rules.

A total of n participants took part in the contest (n ≥ k), and you already know their scores. Calculate how many participants will advance to the next round.

## Input Format
The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 50) separated by a single space.

The second line contains n space-separated integers a1, a2, ..., an (0 ≤ ai ≤ 100), where ai is the score earned by the participant who got the i-th place. The given sequence is non-increasing (that is, for all i from 1 to n - 1 the following condition is fulfilled: ai ≥ ai + 1).

## Output Format
Output the number of participants who advance to the next round.

## Examples
```input
8 5
10 9 8 7 7 7 5 5
```
```output
6
```
-----
```input
4 2
0 0 0 0
```
```output
0
```

## Note
In the first example the participant on the 5th place earned 7 points. As the participant on the 6th place also earned 7 points, there are 6 advancers.

In the second example nobody got a positive score.

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
After the lessons n groups of schoolchildren went outside and decided to visit Polycarpus to celebrate his birthday. We know that the i-th group consists of si friends (1 ≤ si ≤ 4), and they want to go to Polycarpus together. They decided to get there by taxi. Each car can carry at most four passengers. What minimum number of cars will the children need if all members of each group should ride in the same taxi (but one taxi can take more than one group)?

## Input Format
The first line contains integer n (1 ≤ n ≤ 105) — the number of groups of schoolchildren. The second line contains a sequence of integers s1, s2, ..., sn (1 ≤ si ≤ 4). The integers are separated by a space, si is the number of children in the i-th group.

## Output Format
Print the single number — the minimum number of taxis necessary to drive all children to Polycarpus.

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

## Note
In the first test we can sort the children into four cars like this:

- the third group (consisting of four children),
- the fourth group (consisting of three children),
- the fifth group (consisting of three children),
- the first and the second group (consisting of one and two children, correspondingly).

There are other ways to sort the groups into four cars.

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
The Berland University is preparing to celebrate the 256-th anniversary of its founding! A specially appointed Vice Rector for the celebration prepares to decorate the campus. In the center of the campus n ice sculptures were erected. The sculptures are arranged in a circle at equal distances from each other, so they form a regular n-gon. They are numbered in clockwise order with numbers from 1 to n.

The site of the University has already conducted a voting that estimated each sculpture's characteristic of ti — the degree of the sculpture's attractiveness. The values of ti can be positive, negative or zero.

When the university rector came to evaluate the work, he said that this might be not the perfect arrangement. He suggested to melt some of the sculptures so that:

- the remaining sculptures form a regular polygon (the number of vertices should be between 3 and n),
- the sum of the ti values of the remaining sculptures is maximized.

Help the Vice Rector to analyze the criticism — find the maximum value of ti sum which can be obtained in this way. It is allowed not to melt any sculptures at all. The sculptures can not be moved.

## Input Format
The first input line contains an integer n (3 ≤ n ≤ 20000) — the initial number of sculptures. The second line contains a sequence of integers t1, t2, ..., tn, ti — the degree of the i-th sculpture's attractiveness ( - 1000 ≤ ti ≤ 1000). The numbers on the line are separated by spaces.

## Output Format
Print the required maximum sum of the sculptures' attractiveness.

## Examples
```input
8
1 2 -3 4 -5 5 2 3
```
```output
14
```
-----
```input
6
1 -2 3 -4 5 -6
```
```output
9
```
-----
```input
6
1 2 3 4 5 6
```
```output
21
```

## Note
In the first sample it is best to leave every second sculpture, that is, leave sculptures with attractivenesses: 2, 4, 5 и 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
Alice and Bob are playing a game. They are given an array $$$A$$$ of length $$$N$$$. The array consists of integers. They are building a sequence together. In the beginning, the sequence is empty. In one turn a player can remove a number from the left or right side of the array and append it to the sequence. The rule is that the sequence they are building must be strictly increasing. The winner is the player that makes the last move. Alice is playing first. Given the starting array, under the assumption that they both play optimally, who wins the game?

## Input Format
The first line contains one integer $$$N$$$ ($$$1 \leq N \leq 2*10^5$$$) - the length of the array $$$A$$$.

The second line contains $$$N$$$ integers $$$A_1$$$, $$$A_2$$$,...,$$$A_N$$$ ($$$0 \leq A_i \leq 10^9$$$)

## Output Format
The first and only line of output consists of one string, the name of the winner. If Alice won, print "Alice", otherwise, print "Bob".

## Examples
```input
1
5
```
```output
Alice
```
-----
```input
3
5 4 5
```
```output
Alice
```
-----
```input
6
5 8 2 1 10 9
```
```output
Bob
```

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
On the great island of Baltia, there live $$$N$$$ people, numbered from $$$1$$$ to $$$N$$$. There are exactly $$$M$$$ pairs of people that are friends with each other. The people of Baltia want to organize a successful party, but they have very strict rules on what a party is and when the party is successful. On the island of Baltia, a party is a gathering of exactly $$$5$$$ people. The party is considered to be successful if either all the people at the party are friends with each other (so that they can all talk to each other without having to worry about talking to someone they are not friends with) or no two people at the party are friends with each other (so that everyone can just be on their phones without anyone else bothering them). Please help the people of Baltia organize a successful party or tell them that it's impossible to do so.

## Input Format
The first line contains two integer numbers, $$$N$$$ ($$$5 \leq N \leq 2*10^5$$$) and $$$M$$$ ($$$0 \leq M \leq 2*10^5$$$) – the number of people that live in Baltia, and the number of friendships. The next $$$M$$$ lines each contains two integers $$$U_i$$$ and $$$V_i$$$ ($$$1 \leq U_i,V_i \leq N$$$) – meaning that person $$$U_i$$$ is friends with person $$$V_i$$$. Two friends can not be in the list of friends twice (no pairs are repeated) and a person can be friends with themselves ($$$U_i \ne V_i$$$).

## Output Format
If it's possible to organize a successful party, print $$$5$$$ numbers indicating which $$$5$$$ people should be invited to the party. If it's not possible to organize a successful party, print $$$-1$$$ instead. If there are multiple successful parties possible, print any.

## Examples
```input
6 3
1 4
4 2
5 4
```
```output
1 2 3 5 6
```
-----
```input
5 4
1 2
2 3
3 4
4 5
```
```output
-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 have received data from a Bubble bot. You know your task is to make factory facilities, but before you even start, you need to know how big the factory is and how many rooms it has. When you look at the data you see that you have the dimensions of the construction, which is in rectangle shape: N x M.

Then in the next N lines you have M numbers. These numbers represent factory tiles and they can go from 0 to 15. Each of these numbers should be looked in its binary form. Because from each number you know on which side the tile has walls. For example number 10 in it's binary form is 1010, which means that it has a wall from the North side, it doesn't have a wall from the East, it has a wall on the South side and it doesn't have a wall on the West side. So it goes North, East, South, West.

It is guaranteed that the construction always has walls on it's edges. The input will be correct.

Your task is to print the size of the rooms from biggest to smallest.

## Input Format
The first line has two numbers which are N and M, the size of the construction. Both are integers:

$$$n$$$ ($$$1 \leq n \leq 10^3$$$)

$$$m$$$ ($$$1 \leq m \leq 10^3$$$)

Next N x M numbers represent each tile of construction.

## Output Format
Once you finish processing the data your output consists of one line sorted from biggest to smallest room sizes.

## Examples
```input
4 5
9 14 11 12 13
5 15 11 6 7
5 9 14 9 14
3 2 14 3 14
```
```output
9 4 4 2 1
```

Now solve the problem and return the code.