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
You are given a sequence of positive integers a1, a2, ..., an. Find all such indices i, that the i-th element equals the arithmetic mean of all other elements (that is all elements except for this one).

## Input Format
The first line contains the integer n (2 ≤ n ≤ 2·105). The second line contains elements of the sequence a1, a2, ..., an (1 ≤ ai ≤ 1000). All the elements are positive integers.

## Output Format
Print on the first line the number of the sought indices. Print on the second line the sought indices in the increasing order. All indices are integers from 1 to n.

If the sought elements do not exist, then the first output line should contain number 0. In this case you may either not print the second line or print an empty line.

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

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
Let's assume that we have a pair of numbers (a, b). We can get a new pair (a + b, b) or (a, a + b) from the given pair in a single step.

Let the initial pair of numbers be (1,1). Your task is to find number k, that is, the least number of steps needed to transform (1,1) into the pair where at least one number equals n.

## Input Format
The input contains the only integer n (1 ≤ n ≤ 106).

## Output Format
Print the only integer k.

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

## Note
The pair (1,1) can be transformed into a pair containing 5 in three moves: (1,1)  →  (1,2)  →  (3,2)  →  (5,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
There are n players sitting at a round table. All of them have s cards of n colors in total. Besides, initially the first person had cards of only the first color, the second one had cards of only the second color and so on. They can swap the cards by the following rules:

- as the players swap, a player can give a card of his color only;
- a player can't accept a card of a color he already has (particularly, he can't take cards of his color, no matter whether he has given out all of them or not);
- during one swap a pair of people swaps cards (each person gives one card and takes one card).

The aim of all n people is as follows: each of them should give out all the cards he had initially (that is, all cards of his color). Your task is to denote whether such sequence of swaps is possible. If the answer is positive, you should list all the swaps.

## Input Format
The first line contains integers n (1 ≤ n ≤ 200000) and s (1 ≤ s ≤ 200000). The second line contains n numbers, the i-th number stands for how many cards the i-th player has by the moment the game starts. It is possible that a player has no cards initially.

## Output Format
On the first line print "No" if such sequence of swaps is impossible. Otherwise, print "Yes". If the answer is positive, next print number k — the number of the swaps. Then on k lines describe the swaps by pairs of indices of the swapping players. Print the swaps and the numbers of the swaps in any order.

## Examples
```input
4 8
2 2 2 2
```
```output
Yes
4
4 3
4 2
1 3
1 2
```
-----
```input
6 12
1 1 2 2 3 3
```
```output
Yes
6
6 5
6 4
6 3
5 4
5 3
2 1
```
-----
```input
5 5
0 0 0 0 5
```
```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 positive integers $$$n$$$ ($$$1 \le n \le 10^9$$$) and $$$k$$$ ($$$1 \le k \le 100$$$). Represent the number $$$n$$$ as the sum of $$$k$$$ positive integers of the same parity (have the same remainder when divided by $$$2$$$).

In other words, find $$$a_1, a_2, \ldots, a_k$$$ such that all $$$a_i>0$$$, $$$n = a_1 + a_2 + \ldots + a_k$$$ and either all $$$a_i$$$ are even or all $$$a_i$$$ are odd at the same time.

If such a representation does not exist, then report it.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the input. Next, $$$t$$$ test cases are given, one per line.

Each test case is two positive integers $$$n$$$ ($$$1 \le n \le 10^9$$$) and $$$k$$$ ($$$1 \le k \le 100$$$).

## Output Format
For each test case print:

- YES and the required values $$$a_i$$$, if the answer exists (if there are several answers, print any of them);
- NO if the answer does not exist.

The letters in the words YES and NO can be printed in any case.

## Examples
```input
8
10 3
100 4
8 7
97 2
8 8
3 10
5 3
1000000000 9
```
```output
YES
4 2 4
YES
55 5 5 35
NO
NO
YES
1 1 1 1 1 1 1 1
NO
YES
3 1 1
YES
111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111120
```

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 positive integers $$$n$$$ and $$$k$$$. Print the $$$k$$$-th positive integer that is not divisible by $$$n$$$.

For example, if $$$n=3$$$, and $$$k=7$$$, then all numbers that are not divisible by $$$3$$$ are: $$$1, 2, 4, 5, 7, 8, 10, 11, 13 \dots$$$. The $$$7$$$-th number among them is $$$10$$$.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the input. Next, $$$t$$$ test cases are given, one per line.

Each test case is two positive integers $$$n$$$ ($$$2 \le n \le 10^9$$$) and $$$k$$$ ($$$1 \le k \le 10^9$$$).

## Output Format
For each test case print the $$$k$$$-th positive integer that is not divisible by $$$n$$$.

## Examples
```input
6
3 7
4 12
2 1000000000
7 97
1000000000 1000000000
2 1
```
```output
10
15
1999999999
113
1000000001
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: 64.0 MB

# Problem
Pay attention to the non-standard memory limit in this problem.

In order to cut off efficient solutions from inefficient ones in this problem, the time limit is rather strict. Prefer to use compiled statically typed languages (e.g. C++). If you use Python, then submit solutions on PyPy. Try to write an efficient solution.

The array $$$a=[a_1, a_2, \ldots, a_n]$$$ ($$$1 \le a_i \le n$$$) is given. Its element $$$a_i$$$ is called special if there exists a pair of indices $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le n$$$) such that $$$a_i = a_l + a_{l+1} + \ldots + a_r$$$. In other words, an element is called special if it can be represented as the sum of two or more consecutive elements of an array (no matter if they are special or not).

Print the number of special elements of the given array $$$a$$$.

For example, if $$$n=9$$$ and $$$a=[3,1,4,1,5,9,2,6,5]$$$, then the answer is $$$5$$$:

- $$$a_3=4$$$ is a special element, since $$$a_3=4=a_1+a_2=3+1$$$;
- $$$a_5=5$$$ is a special element, since $$$a_5=5=a_2+a_3=1+4$$$;
- $$$a_6=9$$$ is a special element, since $$$a_6=9=a_1+a_2+a_3+a_4=3+1+4+1$$$;
- $$$a_8=6$$$ is a special element, since $$$a_8=6=a_2+a_3+a_4=1+4+1$$$;
- $$$a_9=5$$$ is a special element, since $$$a_9=5=a_2+a_3=1+4$$$.

Please note that some of the elements of the array $$$a$$$ may be equal — if several elements are equal and special, then all of them should be counted in the answer.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the input. Then $$$t$$$ test cases follow.

Each test case is given in two lines. The first line contains an integer $$$n$$$ ($$$1 \le n \le 8000$$$) — the length of the array $$$a$$$. The second line contains integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

It is guaranteed that the sum of the values of $$$n$$$ for all test cases in the input does not exceed $$$8000$$$.

## Output Format
Print $$$t$$$ numbers — the number of special elements for each of the given arrays.

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

# Problem
Shubham has an array $$$a$$$ of size $$$n$$$, and wants to select exactly $$$x$$$ elements from it, such that their sum is odd. These elements do not have to be consecutive. The elements of the array are not guaranteed to be distinct.

Tell him whether he can do so.

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

The first line of each test case contains two integers $$$n$$$ and $$$x$$$ $$$(1 \le x \le n \le 1000)$$$ — the length of the array and the number of elements you need to choose.

The next line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 1000)$$$ — elements of the array.

## Output Format
For each test case, print "Yes" or "No" depending on whether it is possible to choose $$$x$$$ elements such that their sum is odd.

You may print every letter in any case you want.

## Examples
```input
5
1 1
999
1 1
1000
2 1
51 50
2 2
51 50
3 3
101 102 103
```
```output
Yes
No
Yes
Yes
No
```

## Note
For $$$1$$$st case: We must select element $$$999$$$, and the sum is odd.

For $$$2$$$nd case: We must select element $$$1000$$$, so overall sum is not odd.

For $$$3$$$rd case: We can select element $$$51$$$.

For $$$4$$$th case: We must select both elements $$$50$$$ and $$$51$$$  — so overall sum is odd.

For $$$5$$$th case: We must select all elements  — but overall sum is not odd.

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
Shubham has a binary string $$$s$$$. A binary string is a string containing only characters "0" and "1".

He can perform the following operation on the string any amount of times:

- Select an index of the string, and flip the character at that index. This means, if the character was "0", it becomes "1", and vice versa.

A string is called good if it does not contain "010" or "101" as a subsequence  — for instance, "1001" contains "101" as a subsequence, hence it is not a good string, while "1000" doesn't contain neither "010" nor "101" as subsequences, so it is a good string.

What is the minimum number of operations he will have to perform, so that the string becomes good? It can be shown that with these operations we can make any string good.

A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters.

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

Each of the next $$$t$$$ lines contains a binary string $$$s$$$ $$$(1 \le |s| \le 1000)$$$.

## Output Format
For every string, output the minimum number of operations required to make it good.

## Examples
```input
7
001
100
101
010
0
1
001100
```
```output
0
0
1
1
0
0
2
```

## Note
In test cases $$$1$$$, $$$2$$$, $$$5$$$, $$$6$$$ no operations are required since they are already good strings.

For the $$$3$$$rd test case: "001" can be achieved by flipping the first character  — and is one of the possible ways to get a good string.

For the $$$4$$$th test case: "000" can be achieved by flipping the second character  — and is one of the possible ways to get a good string.

For the $$$7$$$th test case: "000000" can be achieved by flipping the third and fourth characters  — and is one of the possible ways to get a good string.

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
Ayush and Ashish play a game on an unrooted tree consisting of $$$n$$$ nodes numbered $$$1$$$ to $$$n$$$. Players make the following move in turns:

- Select any leaf node in the tree and remove it together with any edge which has this node as one of its endpoints. A leaf node is a node with degree less than or equal to $$$1$$$.

A tree is a connected undirected graph without cycles.

There is a special node numbered $$$x$$$. The player who removes this node wins the game.

Ayush moves first. Determine the winner of the game if each player plays optimally.

## Input Format
The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 10)$$$ — the number of testcases. The description of the test cases follows.

The first line of each testcase contains two integers $$$n$$$ and $$$x$$$ $$$(1\leq n \leq 1000, 1 \leq x \leq n)$$$ — the number of nodes in the tree and the special node respectively.

Each of the next $$$n-1$$$ lines contain two integers $$$u$$$, $$$v$$$ $$$(1 \leq u, v \leq n, \text{ } u \ne v)$$$, meaning that there is an edge between nodes $$$u$$$ and $$$v$$$ in the tree.

## Output Format
For every test case, if Ayush wins the game, print "Ayush", otherwise print "Ashish" (without quotes).

## Examples
```input
1
3 1
2 1
3 1
```
```output
Ashish
```
-----
```input
1
3 2
1 2
1 3
```
```output
Ayush
```

## Note
For the $$$1$$$st test case, Ayush can only remove node $$$2$$$ or $$$3$$$, after which node $$$1$$$ becomes a leaf node and Ashish can remove it in his turn.

For the $$$2$$$nd test case, Ayush can remove node $$$2$$$ in the first move itself.

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
Ashish has a tree consisting of $$$n$$$ nodes numbered $$$1$$$ to $$$n$$$ rooted at node $$$1$$$. The $$$i$$$-th node in the tree has a cost $$$a_i$$$, and binary digit $$$b_i$$$ is written in it. He wants to have binary digit $$$c_i$$$ written in the $$$i$$$-th node in the end.

To achieve this, he can perform the following operation any number of times:

- Select any $$$k$$$ nodes from the subtree of any node $$$u$$$, and shuffle the digits in these nodes as he wishes, incurring a cost of $$$k \cdot a_u$$$. Here, he can choose $$$k$$$ ranging from $$$1$$$ to the size of the subtree of $$$u$$$.

He wants to perform the operations in such a way that every node finally has the digit corresponding to its target.

Help him find the minimum total cost he needs to spend so that after all the operations, every node $$$u$$$ has digit $$$c_u$$$ written in it, or determine that it is impossible.

## Input Format
First line contains a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ denoting the number of nodes in the tree.

$$$i$$$-th line of the next $$$n$$$ lines contains 3 space-separated integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ $$$(1 \leq a_i \leq 10^9, 0 \leq b_i, c_i \leq 1)$$$  — the cost of the $$$i$$$-th node, its initial digit and its goal digit.

Each of the next $$$n - 1$$$ lines contain two integers $$$u$$$, $$$v$$$ $$$(1 \leq u, v \leq n, \text{ } u \ne v)$$$, meaning that there is an edge between nodes $$$u$$$ and $$$v$$$ in the tree.

## Output Format
Print the minimum total cost to make every node reach its target digit, and $$$-1$$$ if it is impossible.

## Examples
```input
5
1 0 1
20 1 0
300 0 1
4000 0 0
50000 1 0
1 2
2 3
2 4
1 5
```
```output
4
```
-----
```input
5
10000 0 1
2000 1 0
300 0 1
40 0 0
1 1 0
1 2
2 3
2 4
1 5
```
```output
24000
```
-----
```input
2
109 0 1
205 0 1
1 2
```
```output
-1
```

## Note
The tree corresponding to samples $$$1$$$ and $$$2$$$ are:

In sample $$$1$$$, we can choose node $$$1$$$ and $$$k = 4$$$ for a cost of $$$4 \cdot 1$$$ = $$$4$$$ and select nodes $$${1, 2, 3, 5}$$$, shuffle their digits and get the desired digits in every node.

In sample $$$2$$$, we can choose node $$$1$$$ and $$$k = 2$$$ for a cost of $$$10000 \cdot 2$$$, select nodes $$${1, 5}$$$ and exchange their digits, and similarly, choose node $$$2$$$ and $$$k = 2$$$ for a cost of $$$2000 \cdot 2$$$, select nodes $$${2, 3}$$$ and exchange their digits to get the desired digits in every node.

In sample $$$3$$$, it is impossible to get the desired digits, because there is no node with digit $$$1$$$ initially.

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 two strings $$$s$$$ and $$$t$$$, each of length $$$n$$$ and consisting of lowercase Latin alphabets. You want to make $$$s$$$ equal to $$$t$$$.

You can perform the following operation on $$$s$$$ any number of times to achieve it —

- Choose any substring of $$$s$$$ and rotate it clockwise once, that is, if the selected substring is $$$s[l,l+1...r]$$$, then it becomes $$$s[r,l,l + 1 ... r - 1]$$$. All the remaining characters of $$$s$$$ stay in their position. For example, on rotating the substring $$$[2,4]$$$ , string "abcde" becomes "adbce".

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Find the minimum number of operations required to convert $$$s$$$ to $$$t$$$, or determine that it's impossible.

## Input Format
The first line of the input contains a single integer $$$t$$$ $$$(1\leq t \leq 2000)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1\leq n \leq 2000)$$$ — the length of the strings.

The second and the third lines contain strings $$$s$$$ and $$$t$$$ respectively.

The sum of $$$n$$$ over all the test cases does not exceed $$$2000$$$.

## Output Format
For each test case, output the minimum number of operations to convert $$$s$$$ to $$$t$$$. If it is not possible to convert $$$s$$$ to $$$t$$$, output $$$-1$$$ instead.

## Examples
```input
6
1
a
a
2
ab
ba
3
abc
cab
3
abc
cba
4
abab
baba
4
abcc
aabc
```
```output
0
1
1
2
1
-1
```

## Note
For the $$$1$$$-st test case, since $$$s$$$ and $$$t$$$ are equal, you don't need to apply any operation.

For the $$$2$$$-nd test case, you only need to apply one operation on the entire string ab to convert it to ba.

For the $$$3$$$-rd test case, you only need to apply one operation on the entire string abc to convert it to cab.

For the $$$4$$$-th test case, you need to apply the operation twice: first on the entire string abc to convert it to cab and then on the substring of length $$$2$$$ beginning at the second character to convert it to cba.

For the $$$5$$$-th test case, you only need to apply one operation on the entire string abab to convert it to baba.

For the $$$6$$$-th test case, it is not possible to convert string $$$s$$$ to $$$t$$$.

Now solve the problem and return the code.