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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
CQXYM is counting permutations length of $$$2n$$$.

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

A permutation $$$p$$$(length of $$$2n$$$) will be counted only if the number of $$$i$$$ satisfying $$$p_i<p_{i+1}$$$ is no less than $$$n$$$. For example:

- Permutation $$$[1, 2, 3, 4]$$$ will count, because the number of such $$$i$$$ that $$$p_i<p_{i+1}$$$ equals $$$3$$$ ($$$i = 1$$$, $$$i = 2$$$, $$$i = 3$$$).
- Permutation $$$[3, 2, 1, 4]$$$ won't count, because the number of such $$$i$$$ that $$$p_i<p_{i+1}$$$ equals $$$1$$$ ($$$i = 3$$$).

CQXYM wants you to help him to count the number of such permutations modulo $$$1000000007$$$ ($$$10^9+7$$$).

In addition, modulo operation is to get the remainder. For example:

- $$$7 \mod 3=1$$$, because $$$7 = 3 \cdot 2 + 1$$$,
- $$$15 \mod 4=3$$$, because $$$15 = 4 \cdot 3 + 3$$$.

## Input Format
The input consists of multiple test cases.

The first line contains an integer $$$t (t \geq 1)$$$ — the number of test cases. The description of the test cases follows.

Only one line of each test case contains an integer $$$n(1 \leq n \leq 10^5)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$

## Output Format
For each test case, print the answer in a single line.

## Examples
```input
4
1
2
9
91234
```
```output
1
12
830455698
890287984
```

## Note
$$$n=1$$$, there is only one permutation that satisfies the condition: $$$[1,2].$$$

In permutation $$$[1,2]$$$, $$$p_1<p_2$$$, and there is one $$$i=1$$$ satisfy the condition. Since $$$1 \geq n$$$, this permutation should be counted. In permutation $$$[2,1]$$$, $$$p_1>p_2$$$. Because $$$0<n$$$, this permutation should not be counted.

$$$n=2$$$, there are $$$12$$$ permutations: $$$[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[2,1,3,4],[2,3,1,4],[2,3,4,1],[2,4,1,3],[3,1,2,4],[3,4,1,2],[4,1,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 c++17.

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

Execution time limit: 5.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two integer arrays of length $$$N$$$, $$$A1$$$ and $$$A2$$$. You are also given $$$Q$$$ queries of 4 types:

1 k l r x: set $$$Ak_i:=min(Ak_i, x)$$$ for each $$$l \leq i \leq r$$$.

2 k l r x: set $$$Ak_i:=max(Ak_i, x)$$$ for each $$$l \leq i \leq r$$$.

3 k l r x: set $$$Ak_i:=Ak_i+x$$$ for each $$$l \leq i \leq r$$$.

4 l r: find the $$$(\sum_{i=l}^r F(A1_i+A2_i)) \% (10^9+7)$$$ where $$$F(k)$$$ is the $$$k$$$-th Fibonacci number ($$$F(0)=0, F(1)=1, F(k)=F(k-1)+F(k-2)$$$), and $$$x \% y$$$ denotes the remainder of the division of $$$x$$$ by $$$y$$$.

You should process these queries and answer each query of the fourth type.

## Input Format
The first line contains two integers $$$N$$$ and $$$Q$$$. ($$$1 \leq N, Q \leq 5 \times 10^4$$$)

The second line contains $$$N$$$ integers, array $$$A1_1, A1_2, \dots A1_N$$$. ($$$0 \leq A1_i \leq 10^6$$$)

The third line contains $$$N$$$ integers, array $$$A2_1, A2_2, \dots A2_N$$$. ($$$0 \leq A2_i \leq 10^6$$$)

The next $$$Q$$$ lines describe the queries. Each line contains 5 or 3 integers, where the first integer denotes the type of the query. ($$$k \in \{1, 2\}$$$, $$$1 \leq l \leq r \leq N$$$)

For queries of type 1 and 2, $$$0 \leq x \leq 10^9$$$ holds.

For queries of type 3, $$$−10^6 \leq x \leq 10^6$$$ holds.

It is guaranteed that after every query each number in arrays $$$A1$$$ and $$$A2$$$ will be nonnegative.

## Output Format
Print the answer to each query of the fourth type, in separate lines.

## Examples
```input
3 4
1 0 2
2 1 0
4 1 3
3 2 2 2 3
1 1 1 3 0
4 1 3
```
```output
4
4
```
-----
```input
5 4
1 3 5 3 2
4 2 1 3 3
4 1 3
4 2 5
2 1 2 4 6
4 2 4
```
```output
18
26
68
```

## Note
In the first example: The answer for the first query is $$$F(1 + 2) + F(0 + 1) + F(2 + 0) = F(3) + F(1) + F(2) = 2 + 1 + 1 = 4$$$. After the second query, the array $$$A2$$$ changes to $$$[2, 4, 0]$$$. After the third query, the array $$$A1$$$ changes to $$$[0, 0, 0]$$$. The answer for the fourth query is $$$F(0 + 2) + F(0 + 4) + F(0 + 0) = F(2) + F(4) + F(0) = 1 + 3 + 0 = 4$$$.

In the second example: The answer for the first query is $$$F(1 + 4) + F(3 + 2) + F(5 + 1) = F(5) + F(5) + F(6) = 5 + 5 + 8 = 18$$$. The answer for the second query is $$$F(3 + 2) + F(5 + 1) + F(3 + 3) + F(2 + 3) = F(5) + F(6) + F(6) + F(5) = 5 + 8 + 8 + 5 = 26$$$. After the third query, the array $$$A1$$$ changes to $$$[1, 6, 6, 6, 2]$$$. The answer for the fourth query is $$$F(6 + 2) + F(6 + 1) + F(6 + 3) = F(8) + F(7) + F(9) = 21 + 13 + 34 = 68$$$.

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 c++17.

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an undirected graph of $$$N$$$ nodes and $$$M$$$ edges, $$$E_1, E_2, \dots E_M$$$.

A connected graph is a cactus if each of it's edges belogs to at most one simple cycle. A graph is a desert if each of it's connected components is a cactus.

Find the number of pairs $$$(L, R)$$$, ($$$1 \leq L \leq R \leq M$$$) such that, if we delete all the edges except for $$$E_L, E_{L+1}, \dots E_R$$$, the graph is a desert.

## Input Format
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$2 \leq N \leq 2.5 \times 10^5$$$, $$$1 \leq M \leq 5 \times 10^5$$$). Each of the next $$$M$$$ lines contains two integers. The $$$i$$$-th line describes the $$$i$$$-th edge. It contains integers $$$U_i$$$ and $$$V_i$$$, the nodes connected by the $$$i$$$-th edge ($$$E_i=(U_i, V_i)$$$). It is guaranteed that $$$1 \leq U_i, V_i \leq N$$$ and $$$U_i \neq V_i$$$.

## Output Format
The output contains one integer number – the answer.

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

## Note
In the second example: Graphs for pairs $$$(1, 1)$$$, $$$(2, 2)$$$ and $$$(3, 3)$$$ are deserts because they don't have any cycles. Graphs for pairs $$$(1, 2)$$$ and $$$(2, 3)$$$ have one cycle of length 2 so they are deserts.

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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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.
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 c++17.

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Shohag has an integer sequence $$$a_1, a_2, \ldots, a_n$$$. He can perform the following operation any number of times (possibly, zero):

- Select any positive integer $$$k$$$ (it can be different in different operations).
- Choose any position in the sequence (possibly the beginning or end of the sequence, or in between any two elements) and insert $$$k$$$ into the sequence at this position.
- This way, the sequence $$$a$$$ changes, and the next operation is performed on this changed sequence.

For example, if $$$a=[3,3,4]$$$ and he selects $$$k = 2$$$, then after the operation he can obtain one of the sequences $$$[\underline{2},3,3,4]$$$, $$$[3,\underline{2},3,4]$$$, $$$[3,3,\underline{2},4]$$$, or $$$[3,3,4,\underline{2}]$$$.

Shohag wants this sequence to satisfy the following condition: for each $$$1 \le i \le |a|$$$, $$$a_i \le i$$$. Here, $$$|a|$$$ denotes the size of $$$a$$$.

Help him to find the minimum number of operations that he has to perform to achieve this goal. We can show that under the constraints of the problem it's always possible to achieve this goal in a finite number of operations.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the initial length of the sequence.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the sequence.

## Output Format
For each test case, print a single integer  — the minimum number of operations needed to perform to achieve the goal mentioned in the statement.

## Examples
```input
4
3
1 3 4
5
1 2 5 7 4
1
1
3
69 6969 696969
```
```output
1
3
0
696966
```

## Note
In the first test case, we have to perform at least one operation, as $$$a_2=3>2$$$. We can perform the operation $$$[1, 3, 4] \rightarrow [1, \underline{2}, 3, 4]$$$ (the newly inserted element is underlined), now the condition is satisfied.

In the second test case, Shohag can perform the following operations:

$$$[1, 2, 5, 7, 4] \rightarrow [1, 2, \underline{3}, 5, 7, 4] \rightarrow [1, 2, 3, \underline{4}, 5, 7, 4] \rightarrow [1, 2, 3, 4, 5, \underline{3}, 7, 4]$$$.

In the third test case, the sequence already satisfies the condition.

Now solve the problem and return the code.