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
Once upon a time a child got a test consisting of multiple-choice questions as homework. A multiple-choice question consists of four choices: A, B, C and D. Each choice has a description, and the child should find out the only one that is correct.

Fortunately the child knows how to solve such complicated test. The child will follow the algorithm:

- If there is some choice whose description at least twice shorter than all other descriptions, or at least twice longer than all other descriptions, then the child thinks the choice is great.
- If there is exactly one great choice then the child chooses it. Otherwise the child chooses C (the child think it is the luckiest choice).

You are given a multiple-choice questions, can you predict child's choose?

## Input Format
The first line starts with "A." (without quotes), then followed the description of choice A. The next three lines contains the descriptions of the other choices in the same format. They are given in order: B, C, D. Please note, that the description goes after prefix "X.", so the prefix mustn't be counted in description's length.

Each description is non-empty and consists of at most 100 characters. Each character can be either uppercase English letter or lowercase English letter, or "_".

## Output Format
Print a single line with the child's choice: "A", "B", "C" or "D" (without quotes).

## Examples
```input
A.VFleaKing_is_the_author_of_this_problem
B.Picks_is_the_author_of_this_problem
C.Picking_is_the_author_of_this_problem
D.Ftiasch_is_cute
```
```output
D
```
-----
```input
A.ab
B.abcde
C.ab
D.abc
```
```output
C
```
-----
```input
A.c
B.cc
C.c
D.c
```
```output
B
```

## Note
In the first sample, the first choice has length 39, the second one has length 35, the third one has length 37, and the last one has length 15. The choice D (length 15) is twice shorter than all other choices', so it is great choice. There is no other great choices so the child will choose D.

In the second sample, no choice is great, so the child will choose the luckiest choice C.

In the third sample, the choice B (length 2) is twice longer than all other choices', so it is great choice. There is no other great choices so the child will choose B.

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
At the children's day, the child came to Picks's house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite set of Picks.

Fortunately, Picks remembers something about his set S:

- its elements were distinct integers from 1 to limit;
- the value of $$\sum_{x \in S} lowbit(x)$$ was equal to sum; here lowbit(x) equals 2k where k is the position of the first one in the binary representation of x. For example, lowbit(100102) = 102, lowbit(100012) = 12, lowbit(100002) = 100002 (binary representation).

Can you help Picks and find any set S, that satisfies all the above conditions?

## Input Format
The first line contains two integers: sum, limit (1 ≤ sum, limit ≤ 105).

## Output Format
In the first line print an integer n (1 ≤ n ≤ 105), denoting the size of S. Then print the elements of set S in any order. If there are multiple answers, print any of them.

If it's impossible to find a suitable set, print -1.

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

## Note
In sample test 1: lowbit(4) = 4, lowbit(5) = 1, 4 + 1 = 5.

In sample test 2: lowbit(1) = 1, lowbit(2) = 2, lowbit(3) = 1, 1 + 2 + 1 = 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Jzzhu have n non-negative integers a1, a2, ..., an. We will call a sequence of indexes i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n) a group of size k.

Jzzhu wonders, how many groups exists such that ai1 & ai2 & ... & aik = 0 (1 ≤ k ≤ n)? Help him and print this number modulo 1000000007 (109 + 7). Operation x & y denotes bitwise AND operation of two numbers.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 106). The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 106).

## Output Format
Output a single integer representing the number of required groups modulo 1000000007 (109 + 7).

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

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
After winning gold and silver in IOI 2014, Akshat and Malvika want to have some fun. Now they are playing a game on a grid made of n horizontal and m vertical sticks.

An intersection point is any point on the grid which is formed by the intersection of one horizontal stick and one vertical stick.

In the grid shown below, n = 3 and m = 3. There are n + m = 6 sticks in total (horizontal sticks are shown in red and vertical sticks are shown in green). There are n·m = 9 intersection points, numbered from 1 to 9.

The rules of the game are very simple. The players move in turns. Akshat won gold, so he makes the first move. During his/her move, a player must choose any remaining intersection point and remove from the grid all sticks which pass through this point. A player will lose the game if he/she cannot make a move (i.e. there are no intersection points remaining on the grid at his/her move).

Assume that both players play optimally. Who will win the game?

## Input Format
The first line of input contains two space-separated integers, n and m (1 ≤ n, m ≤ 100).

## Output Format
Print a single line containing "Akshat" or "Malvika" (without the quotes), depending on the winner of the game.

## Examples
```input
2 2
```
```output
Malvika
```
-----
```input
2 3
```
```output
Malvika
```
-----
```input
3 3
```
```output
Akshat
```

## Note
Explanation of the first sample:

The grid has four intersection points, numbered from 1 to 4.

If Akshat chooses intersection point 1, then he will remove two sticks (1 - 2 and 1 - 3). The resulting grid will look like this.

Now there is only one remaining intersection point (i.e. 4). Malvika must choose it and remove both remaining sticks. After her move the grid will be empty.

In the empty grid, Akshat cannot make any move, hence he will lose.

Since all 4 intersection points of the grid are equivalent, Akshat will lose no matter which one he picks.

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
Being a programmer, you like arrays a lot. For your birthday, your friends have given you an array a consisting of n distinct integers.

Unfortunately, the size of a is too small. You want a bigger array! Your friends agree to give you a bigger array, but only if you are able to answer the following question correctly: is it possible to sort the array a (in increasing order) by reversing exactly one segment of a? See definitions of segment and reversing in the notes.

## Input Format
The first line of the input contains an integer n (1 ≤ n ≤ 105) — the size of array a.

The second line contains n distinct space-separated integers: a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109).

## Output Format
Print "yes" or "no" (without quotes), depending on the answer.

If your answer is "yes", then also print two space-separated integers denoting start and end (start must not be greater than end) indices of the segment to be reversed. If there are multiple ways of selecting these indices, print any of them.

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

## Note
Sample 1. You can reverse the entire array to get [1, 2, 3], which is sorted.

Sample 3. No segment can be reversed such that the array will be sorted.

Definitions

A segment [l, r] of array a is the sequence a[l], a[l + 1], ..., a[r].

If you have an array a of size n and you reverse its segment [l, r], the array will become:

a[1], a[2], ..., a[l - 2], a[l - 1], a[r], a[r - 1], ..., a[l + 1], a[l], a[r + 1], a[r + 2], ..., a[n - 1], a[n].

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
We call a string good, if after merging all the consecutive equal characters, the resulting string is palindrome. For example, "aabba" is good, because after the merging step it will become "aba".

Given a string, you have to find two values:

1. the number of good substrings of even length;
2. the number of good substrings of odd length.

## Input Format
The first line of the input contains a single string of length n (1 ≤ n ≤ 105). Each character of the string will be either 'a' or 'b'.

## Output Format
Print two space-separated integers: the number of good substrings of even length and the number of good substrings of odd length.

## Examples
```input
bb
```
```output
1 2
```
-----
```input
baab
```
```output
2 4
```
-----
```input
babb
```
```output
2 5
```
-----
```input
babaa
```
```output
2 7
```

## Note
In example 1, there are three good substrings ("b", "b", and "bb"). One of them has even length and two of them have odd length.

In example 2, there are six good substrings (i.e. "b", "a", "a", "b", "aa", "baab"). Two of them have even length and four of them have odd length.

In example 3, there are seven good substrings (i.e. "b", "a", "b", "b", "bb", "bab", "babb"). Two of them have even length and five of them have odd length.

Definitions

A substring s[l, r] (1 ≤ l ≤ r ≤ n) of string s = s1s2... sn is string slsl + 1... sr.

A string s = s1s2... sn is a palindrome if it is equal to string snsn - 1... s1.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 256.0 MB

# Problem
Devu wants to decorate his garden with flowers. He has purchased n boxes, where the i-th box contains fi flowers. All flowers in a single box are of the same color (hence they are indistinguishable). Also, no two boxes have flowers of the same color.

Now Devu wants to select exactly s flowers from the boxes to decorate his garden. Devu would like to know, in how many different ways can he select the flowers from each box? Since this number may be very large, he asks you to find the number modulo (109 + 7).

Devu considers two ways different if there is at least one box from which different number of flowers are selected in these two ways.

## Input Format
The first line of input contains two space-separated integers n and s (1 ≤ n ≤ 20, 0 ≤ s ≤ 1014).

The second line contains n space-separated integers f1, f2, ... fn (0 ≤ fi ≤ 1012).

## Output Format
Output a single integer — the number of ways in which Devu can select the flowers modulo (109 + 7).

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

## Note
Sample 1. There are two ways of selecting 3 flowers: {1, 2} and {0, 3}.

Sample 2. There is only one way of selecting 4 flowers: {2, 2}.

Sample 3. There are three ways of selecting 5 flowers: {1, 2, 2}, {0, 3, 2}, and {1, 3, 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
Vasya has n pairs of socks. In the morning of each day Vasya has to put on a pair of socks before he goes to school. When he comes home in the evening, Vasya takes off the used socks and throws them away. Every m-th day (at days with numbers m, 2m, 3m, ...) mom buys a pair of socks to Vasya. She does it late in the evening, so that Vasya cannot put on a new pair of socks before the next day. How many consecutive days pass until Vasya runs out of socks?

## Input Format
The single line contains two integers n and m (1 ≤ n ≤ 100; 2 ≤ m ≤ 100), separated by a space.

## Output Format
Print a single integer — the answer to the problem.

## Examples
```input
2 2
```
```output
3
```
-----
```input
9 3
```
```output
13
```

## Note
In the first sample Vasya spends the first two days wearing the socks that he had initially. Then on day three he puts on the socks that were bought on day two.

In the second sample Vasya spends the first nine days wearing the socks that he had initially. Then he spends three days wearing the socks that were bought on the third, sixth and ninth days. Than he spends another day wearing the socks that were bought on the twelfth day.

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
Little Dima misbehaved during a math lesson a lot and the nasty teacher Mr. Pickles gave him the following problem as a punishment.

Find all integer solutions x (0 < x < 109) of the equation:

x = b·s(x)a + c,

where a, b, c are some predetermined constant values and function s(x) determines the sum of all digits in the decimal representation of number x.

The teacher gives this problem to Dima for each lesson. He changes only the parameters of the equation: a, b, c. Dima got sick of getting bad marks and he asks you to help him solve this challenging problem.

## Input Format
The first line contains three space-separated integers: a, b, c (1 ≤ a ≤ 5; 1 ≤ b ≤ 10000;  - 10000 ≤ c ≤ 10000).

## Output Format
Print integer n — the number of the solutions that you've found. Next print n integers in the increasing order — the solutions of the given equation. Print only integer solutions that are larger than zero and strictly less than 109.

## Examples
```input
3 2 8
```
```output
3
10 2008 13726
```
-----
```input
1 2 -18
```
```output
0
```
-----
```input
2 2 -1
```
```output
4
1 31 337 967
```

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
Little Victor adores the sets theory. Let us remind you that a set is a group of numbers where all numbers are pairwise distinct. Today Victor wants to find a set of integers S that has the following properties:

- for all x $$( x \in S )$$ the following inequality holds l ≤ x ≤ r;
- 1 ≤ |S| ≤ k;
- lets denote the i-th element of the set S as si; value $$f(S) = s_1 \oplus s_2 \oplus \cdots \oplus s_{|S|}$$ must be as small as possible.

Help Victor find the described set.

## Input Format
The first line contains three space-separated integers l, r, k (1 ≤ l ≤ r ≤ 1012; 1 ≤ k ≤ min(106, r - l + 1)).

## Output Format
Print the minimum possible value of f(S). Then print the cardinality of set |S|. Then print the elements of the set in any order.

If there are multiple optimal sets, you can print any of them.

## Examples
```input
8 15 3
```
```output
1
2
10 11
```
-----
```input
8 30 7
```
```output
0
5
14 9 28 11 16
```

## Note
Operation $$x \oplus y$$ represents the operation of bitwise exclusive OR. In other words, it is the XOR operation.

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
Roland loves growing flowers. He has recently grown a beautiful rose at point (0, 0) of the Cartesian coordinate system. The rose is so beautiful that Roland is afraid that the evil forces can try and steal it.

To protect the rose, Roland wants to build n watch towers. Let's assume that a tower is a point on the plane at the distance of at most r from the rose. Besides, Roland assumes that the towers should be built at points with integer coordinates and the sum of squares of distances between all pairs of towers must be as large as possible. Note, that Roland may build several towers at the same point, also he may build some of them at point (0, 0).

Help Roland build the towers at the integer points so that the sum of squares of distances between all towers is maximum possible. Note that the distance in this problem is defined as the Euclidian distance between points.

## Input Format
The first line contains two integers, n and r (2 ≤ n ≤ 8; 1 ≤ r ≤ 30).

## Output Format
In the first line print an integer — the maximum possible sum of squared distances. In the i-th of the following n lines print two integers, xi, yi — the coordinates of the i-th tower. Each tower must be inside or on the border of the circle with radius r. Note that there may be several towers located at the same point of the plane, also some towers can be located at point (0, 0).

If there are multiple valid optimal arrangements, choose any of them.

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

Now solve the problem and return the code.