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
Alice and Bob are playing a game in an array $$$a$$$ of size $$$n$$$.

They take turns to do operations, with Alice starting first. The player who can not operate will lose. At first, a variable $$$mx$$$ is set to $$$0$$$.

In one operation, a player can do:

- Choose an index $$$i$$$ ($$$1 \le i \le n$$$) such that $$$a_{i} \geq mx$$$ and set $$$mx$$$ to $$$a_{i}$$$. Then, set $$$a_{i}$$$ to $$$0$$$.

Determine whether Alice has a winning strategy.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases.

For each test case:

- The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 50$$$) — the size of the array.
- The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the elements of the array.

## Output Format
For each test case, if Alice has a winning strategy, output "YES". Otherwise, output "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

## Examples
```input
5
2
2 1
2
1 1
3
3 3 3
4
3 3 4 4
4
1 2 2 2
```
```output
YES
NO
YES
NO
YES
```

## Note
In the first test case, Alice can choose $$$i=1$$$ since $$$a_1=2 \ge mx=0$$$.

After Alice's operation, $$$a=[0,1]$$$ and $$$mx=2$$$. Bob can not do any operation. Alice wins.

In the second test case, Alice doesn't have a winning strategy.

For example, if Alice chooses $$$i=1$$$, after Alice's operation: $$$a=[0,1]$$$ and $$$mx=1$$$. Then, Bob can choose $$$i=2$$$ since $$$a_2=1 \ge mx=1$$$. After Bob's operation: $$$a=[0,0]$$$ and $$$mx=1$$$. Alice can not do any operation. Bob wins.

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 an array $$$b$$$ of size $$$m$$$, we define:

- the maximum prefix position of $$$b$$$ is the smallest index $$$i$$$ that satisfies $$$b_1+\ldots+b_i=\max_{j=1}^{m}(b_1+\ldots+b_j)$$$;
- the maximum suffix position of $$$b$$$ is the largest index $$$i$$$ that satisfies $$$b_i+\ldots+b_m=\max_{j=1}^{m}(b_j+\ldots+b_m)$$$.

You are given three integers $$$n$$$, $$$x$$$, and $$$y$$$ ($$$x > y$$$). Construct an array $$$a$$$ of size $$$n$$$ satisfying:

- $$$a_i$$$ is either $$$1$$$ or $$$-1$$$ for all $$$1 \le i \le n$$$;
- the maximum prefix position of $$$a$$$ is $$$x$$$;
- the maximum suffix position of $$$a$$$ is $$$y$$$.

If there are multiple arrays that meet the conditions, print any. It can be proven that such an array always exists under the given conditions.

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

For each test case:

- The only line contains three integers $$$n$$$, $$$x$$$, and $$$y$$$ ($$$2 \leq n \leq 10^5, 1 \le y \lt x \le n)$$$.

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

## Output Format
For each test case, output $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ in a new line.

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

## Note
In the second test case,

- $$$i=x=4$$$ is the smallest index that satisfies $$$a_1+\ldots +a_i=\max_{j=1}^{n}(a_1+\ldots+a_j)=2$$$;
- $$$i=y=3$$$ is the greatest index that satisfies $$$a_i+\ldots +a_n=\max_{j=1}^{n}(a_j+\ldots+a_n)=2$$$.

Thus, the array $$$a=[1,-1,1,1]$$$ is considered correct.

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
You are given an array $$$a$$$ of size $$$n$$$.

There is an $$$n \times n$$$ grid. In the $$$i$$$-th row, the first $$$a_i$$$ cells are black and the other cells are white. In other words, note $$$(i,j)$$$ as the cell in the $$$i$$$-th row and $$$j$$$-th column, cells $$$(i,1), (i,2), \ldots, (i,a_i)$$$ are black, and cells $$$(i,a_i+1), \ldots, (i,n)$$$ are white.

You can do the following operations any number of times in any order:

- Dye a $$$2 \times 2$$$ subgrid white;
- Dye a whole row white. Note you can not dye a whole column white.

Find the minimum number of operations to dye all cells white.

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

For each test case:

- The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the size of the array $$$a$$$.
- The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$).

It's guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output a single integer — the minimum number of operations to dye all cells white.

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

## Note
In the first test case, you don't need to do any operation.

In the second test case, you can do:

- Dye $$$(1,1), (1,2), (2,1)$$$, and $$$(2,2)$$$ white;
- Dye $$$(2,3), (2,4), (3,3)$$$, and $$$(3,4)$$$ white;
- Dye $$$(3,1), (3,2), (4,1)$$$, and $$$(4,2)$$$ white.

It can be proven $$$3$$$ is the minimum number of operations.

In the third test case, you can do:

- Dye the first row white;
- Dye $$$(2,1), (2,2), (3,1)$$$, and $$$(3,2)$$$ white.

It can be proven $$$2$$$ is the minimum number of operations.

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: 8.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an array $$$a$$$ of size $$$n$$$.

A segment $$$[l, r](1 \le l < r \le n)$$$ is called a polygonal segment only if the following conditions hold:

- $$$(r-l+1) \geq 3$$$;
- Considering $$$a_l, a_{l+1}, \ldots, a_r$$$ as side lengths, these sides can form a polygon with $$$(r-l+1)$$$ sides.

Process $$$q$$$ queries of two types:

- "1 l r": find the length of the longest segment among all polygonal segments $$$[l_0,r_0]$$$ satisfying $$$l \le l_0 \le r_0 \le r$$$. If there is no such polygonal segment, output $$$-1$$$ instead;
- "2 i x": assign $$$a_i := x$$$.

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

For each test case:

- The first line of each testcase contains two integers $$$n$$$, $$$q$$$ ($$$4 \le n \le 2\cdot 10^5$$$, $$$1 \le q \le 10^5$$$);
- The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$);
- The following $$$q$$$ lines contain the description of queries. Each line is of one of two types:  "1 l r" ($$$1 \le l < r \le n$$$, $$$r-l+1\ge 3$$$);  "2 i x" ($$$1 \le i \le n$$$, $$$1 \le x \le 10^{12}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$, and the sum of $$$q$$$ over all test cases will not exceed $$$10^5$$$.

## Output Format
For each query, if there is no suitable segment, output $$$-1$$$ in a new line. Otherwise, output the length of the longest segment satisfying the condition above in a new line.

## Examples
```input
2
5 6
3 1 2 2 8
1 1 3
1 1 4
1 1 5
2 1 5
1 1 4
1 1 5
4 10
500000000000 500000000000 1000000000000 500000000000
1 1 3
1 2 4
1 1 4
2 1 499999999999
2 3 999999999999
1 1 3
1 2 4
1 1 4
2 3 1000000000000
1 1 3
```
```output
-1
4
4
3
5
-1
-1
4
-1
3
4
-1
```

## Note
In the first query of the first test case, there is no polygonal segment under the given condition. For example, considering segment $$$[1,3]$$$, you can not form a triangle with side lengths of $$$a_1=3$$$, $$$a_2=1$$$, and $$$a_3=2$$$.

In the second query of the first test case, the longest polygonal segment is $$$[1,4]$$$. You can form a quadrilateral with side lengths of $$$a_1=3$$$, $$$a_2=1$$$, $$$a_3=2$$$, and $$$a_4=2$$$.

An example of a quadrilateral with side lengths of $$$3$$$, $$$1$$$, $$$2$$$, and $$$2$$$.

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
This problem's actual name, "Lexicographically Largest Palindromic Subsequence" is too long to fit into the page headline.

You are given string s consisting of lowercase English letters only. Find its lexicographically largest palindromic subsequence.

We'll call a non-empty string s[p1p2... pk] = sp1sp2... spk (1  ≤  p1 < p2 < ... < pk  ≤  |s|) a subsequence of string s = s1s2... s|s|, where |s| is the length of string s. For example, strings "abcb", "b" and "abacaba" are subsequences of string "abacaba".

String x = x1x2... x|x| is lexicographically larger than string y = y1y2... y|y| if either |x| > |y| and x1 = y1, x2 = y2, ..., x|y| = y|y|, or there exists such number r (r < |x|, r < |y|) that x1 = y1, x2 = y2, ..., xr = yr and xr  +  1 > yr  +  1. Characters in the strings are compared according to their ASCII codes. For example, string "ranger" is lexicographically larger than string "racecar" and string "poster" is lexicographically larger than string "post".

String s = s1s2... s|s| is a palindrome if it matches string rev(s) = s|s|s|s| - 1... s1. In other words, a string is a palindrome if it reads the same way from left to right and from right to left. For example, palindromic strings are "racecar", "refer" and "z".

## Input Format
The only input line contains a non-empty string s consisting of lowercase English letters only. Its length does not exceed 10.

## Output Format
Print the lexicographically largest palindromic subsequence of string s.

## Examples
```input
radar
```
```output
rr
```
-----
```input
bowwowwow
```
```output
wwwww
```
-----
```input
codeforces
```
```output
s
```
-----
```input
mississipp
```
```output
ssss
```

## Note
Among all distinct subsequences of string "radar" the following ones are palindromes: "a", "d", "r", "aa", "rr", "ada", "rar", "rdr", "raar" and "radar". The lexicographically largest of them is "rr".

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
Several ages ago Berland was a kingdom. The King of Berland adored math. That's why, when he first visited one of his many palaces, he first of all paid attention to the floor in one hall. The floor was tiled with hexagonal tiles.

The hall also turned out hexagonal in its shape. The King walked along the perimeter of the hall and concluded that each of the six sides has a, b, c, a, b and c adjacent tiles, correspondingly.

To better visualize the situation, look at the picture showing a similar hexagon for a = 2, b = 3 and c = 4.

According to the legend, as the King of Berland obtained the values a, b and c, he almost immediately calculated the total number of tiles on the hall floor. Can you do the same?

## Input Format
The first line contains three integers: a, b and c (2 ≤ a, b, c ≤ 1000).

## Output Format
Print a single number — the total number of tiles on the hall floor.

## Examples
```input
2 3 4
```
```output
18
```

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
One day n students come to the stadium. They want to play football, and for that they need to split into teams, the teams must have an equal number of people.

We know that this group of people has archenemies. Each student has at most two archenemies. Besides, if student A is an archenemy to student B, then student B is an archenemy to student A.

The students want to split so as no two archenemies were in one team. If splitting in the required manner is impossible, some students will have to sit on the bench.

Determine the minimum number of students you will have to send to the bench in order to form the two teams in the described manner and begin the game at last.

## Input Format
The first line contains two integers n and m (2 ≤ n ≤ 100, 1 ≤ m ≤ 100) — the number of students and the number of pairs of archenemies correspondingly.

Next m lines describe enmity between students. Each enmity is described as two numbers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — the indexes of the students who are enemies to each other. Each enmity occurs in the list exactly once. It is guaranteed that each student has no more than two archenemies.

You can consider the students indexed in some manner with distinct integers from 1 to n.

## Output Format
Print a single integer — the minimum number of students you will have to send to the bench in order to start the game.

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

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 new Berland businessman Vitaly is going to open a household appliances' store. All he's got to do now is to hire the staff.

The store will work seven days a week, but not around the clock. Every day at least k people must work in the store.

Berland has a law that determines the order of working days and non-working days. Namely, each employee must work for exactly n consecutive days, then rest for exactly m days, then work for n more days and rest for m more, and so on. Vitaly doesn't want to break the law. Fortunately, there is a loophole: the law comes into force on the day when the employee is hired. For example, if an employee is hired on day x, then he should work on days [x, x + 1, ..., x + n - 1], [x + m + n, x + m + n + 1, ..., x + m + 2n - 1], and so on. Day x can be chosen arbitrarily by Vitaly.

There is one more thing: the key to the store. Berland law prohibits making copies of keys, so there is only one key. Vitaly is planning to entrust the key to the store employees. At the same time on each day the key must be with an employee who works that day — otherwise on this day no one can get inside the store. During the day the key holder can give the key to another employee, if he also works that day. The key will handed to the first hired employee at his first working day.

Each employee has to be paid salary. Therefore, Vitaly wants to hire as few employees as possible provided that the store can operate normally on each day from 1 to infinity. In other words, on each day with index from 1 to infinity, the store must have at least k working employees, and one of the working employees should have the key to the store.

Help Vitaly and determine the minimum required number of employees, as well as days on which they should be hired.

## Input Format
The first line contains three integers n, m and k (1 ≤ m ≤ n ≤ 1000, n ≠ 1, 1 ≤ k ≤ 1000).

## Output Format
In the first line print a single integer z — the minimum required number of employees.

In the second line print z positive integers, separated by spaces: the i-th integer ai (1 ≤ ai ≤ 104) should represent the number of the day, on which Vitaly should hire the i-th employee.

If there are multiple answers, print any of them.

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

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
You know that the Martians use a number system with base k. Digit b (0 ≤ b < k) is considered lucky, as the first contact between the Martians and the Earthlings occurred in year b (by Martian chronology).

A digital root d(x) of number x is a number that consists of a single digit, resulting after cascading summing of all digits of number x. Word "cascading" means that if the first summing gives us a number that consists of several digits, then we sum up all digits again, and again, until we get a one digit number.

For example, d(35047) = d((3 + 5 + 0 + 4)7) = d(157) = d((1 + 5)7) = d(67) = 67. In this sample the calculations are performed in the 7-base notation.

If a number's digital root equals b, the Martians also call this number lucky.

You have string s, which consists of n digits in the k-base notation system. Your task is to find, how many distinct substrings of the given string are lucky numbers. Leading zeroes are permitted in the numbers.

Note that substring s[i... j] of the string s = a1a2... an (1 ≤ i ≤ j ≤ n) is the string aiai + 1... aj. Two substrings s[i1... j1] and s[i2... j2] of the string s are different if either i1 ≠ i2 or j1 ≠ j2.

## Input Format
The first line contains three integers k, b and n (2 ≤ k ≤ 109, 0 ≤ b < k, 1 ≤ n ≤ 105).

The second line contains string s as a sequence of n integers, representing digits in the k-base notation: the i-th integer equals ai (0 ≤ ai < k) — the i-th digit of string s. The numbers in the lines are space-separated.

## Output Format
Print a single integer — the number of substrings that are lucky numbers.

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
10 5 6
3 2 0 5 6 1
```
```output
5
```
-----
```input
7 6 4
3 5 0 4
```
```output
1
```
-----
```input
257 0 3
0 0 256
```
```output
3
```

## Note
In the first sample the following substrings have the sought digital root: s[1... 2] = "3 2", s[1... 3] = "3 2 0", s[3... 4] = "0 5", s[4... 4] = "5" and s[2... 6] = "2 0 5 6 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 permutation is a sequence of integers p1, p2, ..., pn, consisting of n distinct positive integers, each of them doesn't exceed n. Let's denote the i-th element of permutation p as pi. We'll call number n the size of permutation p1, p2, ..., pn.

Nickolas adores permutations. He likes some permutations more than the others. He calls such permutations perfect. A perfect permutation is such permutation p that for any i (1 ≤ i ≤ n) (n is the permutation size) the following equations hold ppi = i and pi ≠ i. Nickolas asks you to print any perfect permutation of size n for the given n.

## Input Format
A single line contains a single integer n (1 ≤ n ≤ 100) — the permutation size.

## Output Format
If a perfect permutation of size n doesn't exist, print a single integer -1. Otherwise print n distinct integers from 1 to n, p1, p2, ..., pn — permutation p, that is perfect. Separate printed numbers by whitespaces.

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

Now solve the problem and return the code.