Your task is to process some data.
You are given 3 integers a , b , c and a string s. Output result of a + b + c and string s with a half-width break.

Constrains

• 1\leq a, b, c \leq 1,000
• 1\leq|s|\leq 100

Output the result of a+b+c and string s with a half-width break in one line.

Input Example #1

1
2 3
test

Output Example #1

6 test

• 1+2+3 equals to 6.

Input Example #2

72
128 256
myonmyon

Output Example #2

456 myonmyon

• 72+128+256 equals to 456.

Problem Statement

AtCoDeer the deer found two positive integers, a and b. Determine whether the product of a and b is even or odd.

Constraints

• 1 ≤ a,b ≤ 10000
• a and b are integers.

Sample Input 1

3 4

Sample Output 1

Even

As 3 × 4 = 12 is even, print Even.

Sample Input 2

1 21

Sample Output 2

Odd

As 1 × 21 = 21 is odd, print Odd.

Problem Statement

Snuke has a grid consisting of three squares numbered 1, 2 and 3. In each square, either 0 or 1 is written. The number written in Square i is s_i.

Snuke will place a marble on each square that says 1. Find the number of squares on which Snuke will place a marble.

Constraints

• Each of s_1, s_2 and s_3 is either 1 or 0.

Sample Input 1

101

Sample Output 1

2

• A marble will be placed on Square 1 and 3.

Sample Input 2

000

Sample Output 2

0

• No marble will be placed on any square.

Problem Statement

There are N positive integers written on a blackboard: A_1, ..., A_N.

Snuke can perform the following operation when all integers on the blackboard are even:

• Replace each integer X on the blackboard by X divided by 2.

Find the maximum possible number of operations that Snuke can perform.

Constraints

• 1 \leq N \leq 200
• 1 \leq A_i \leq 10^9

Sample Input 1

3
8 12 40

Sample Output 1

2

Initially, [8, 12, 40] are written on the blackboard. Since all those integers are even, Snuke can perform the operation.

After the operation is performed once, [4, 6, 20] are written on the blackboard. Since all those integers are again even, he can perform the operation.

After the operation is performed twice, [2, 3, 10] are written on the blackboard. Now, there is an odd number 3 on the blackboard, so he cannot perform the operation any more.

Thus, Snuke can perform the operation at most twice.

Sample Input 2

4
5 6 8 10

Sample Output 2

0

Since there is an odd number 5 on the blackboard already in the beginning, Snuke cannot perform the operation at all.

Sample Input 3

6
382253568 723152896 37802240 379425024 404894720 471526144

Sample Output 3

8

Problem Statement

You have A 500-yen coins, B 100-yen coins and C 50-yen coins (yen is the currency of Japan). In how many ways can we select some of these coins so that they are X yen in total?

Coins of the same kind cannot be distinguished. Two ways to select coins are distinguished when, for some kind of coin, the numbers of that coin are different.

Constraints

• 0 \leq A, B, C \leq 50
• A + B + C \geq 1
• 50 \leq X \leq 20 000
• A, B and C are integers.
• X is a multiple of 50.

Sample Input 1

2
2
2
100

Sample Output 1

2

There are two ways to satisfy the condition:

• Select zero 500-yen coins, one 100-yen coin and zero 50-yen coins.
• Select zero 500-yen coins, zero 100-yen coins and two 50-yen coins.

Sample Input 2

5
1
0
150

Sample Output 2

0

Note that the total must be exactly X yen.

Sample Input 3

30
40
50
6000

Sample Output 3

213

Problem Statement

Find the sum of the integers between 1 and N (inclusive), whose sum of digits written in base 10 is between A and B (inclusive).

Constraints

• 1 \leq N \leq 10^4
• 1 \leq A \leq B \leq 36
• All input values are integers.

Sample Input 1

20 2 5

Sample Output 1

84

Among the integers not greater than 20, the ones whose sums of digits are between 2 and 5, are: 2,3,4,5,11,12,13,14 and 20. We should print the sum of these, 84.

Sample Input 2

10 1 2

Sample Output 2

13

Sample Input 3

100 4 16

Sample Output 3

4554

Problem Statement

We have N cards. A number a_i is written on the i-th card.
Alice and Bob will play a game using these cards. In this game, Alice and Bob alternately take one card. Alice goes first.
The game ends when all the cards are taken by the two players, and the score of each player is the sum of the numbers written on the cards he/she has taken. When both players take the optimal strategy to maximize their scores, find Alice's score minus Bob's score.

Constraints

• N is an integer between 1 and 100 (inclusive).
• a_i \ (1 \leq i \leq N) is an integer between 1 and 100 (inclusive).

Sample Input 1

2
3 1

Sample Output 1

2

First, Alice will take the card with 3. Then, Bob will take the card with 1. The difference of their scores will be 3 - 1 = 2.

Sample Input 2

3
2 7 4

Sample Output 2

5

First, Alice will take the card with 7. Then, Bob will take the card with 4. Lastly, Alice will take the card with 2. The difference of their scores will be 7 - 4 + 2 = 5. The difference of their scores will be 3 - 1 = 2.

Sample Input 3

4
20 18 2 18

Sample Output 3

18

Problem Statement

An X-layered kagami mochi (X ≥ 1) is a pile of X round mochi (rice cake) stacked vertically where each mochi (except the bottom one) has a smaller diameter than that of the mochi directly below it. For example, if you stack three mochi with diameters of 10, 8 and 6 centimeters from bottom to top in this order, you have a 3-layered kagami mochi; if you put just one mochi, you have a 1-layered kagami mochi.

Lunlun the dachshund has N round mochi, and the diameter of the i-th mochi is d_i centimeters. When we make a kagami mochi using some or all of them, at most how many layers can our kagami mochi have?

Constraints

• 1 ≤ N ≤ 100
• 1 ≤ d_i ≤ 100
• All input values are integers.

Sample Input 1

4
10
8
8
6

Sample Output 1

3

If we stack the mochi with diameters of 10, 8 and 6 centimeters from bottom to top in this order, we have a 3-layered kagami mochi, which is the maximum number of layers.

Sample Input 2

3
15
15
15

Sample Output 2

1

When all the mochi have the same diameter, we can only have a 1-layered kagami mochi.

Sample Input 3

7
50
30
50
100
50
80
30

Sample Output 3

4

Problem Statement

The commonly used bills in Japan are 10000-yen, 5000-yen and 1000-yen bills. Below, the word "bill" refers to only these.

According to Aohashi, he received an otoshidama (New Year money gift) envelope from his grandfather that contained N bills for a total of Y yen, but he may be lying. Determine whether such a situation is possible, and if it is, find a possible set of bills contained in the envelope. Assume that his grandfather is rich enough, and the envelope was large enough.

Constraints

• 1 ≤ N ≤ 2000
• 1000 ≤ Y ≤ 2 × 10^7
• N is an integer.
• Y is a multiple of 1000.

Sample Input 1

9 45000

Sample Output 1

4 0 5

If the envelope contained 4 10000-yen bills and 5 1000-yen bills, he had 9 bills and 45000 yen in total. It is also possible that the envelope contained 9 5000-yen bills, so the output 0 9 0 is also correct.

Sample Input 2

20 196000

Sample Output 2

-1 -1 -1

When the envelope contained 20 bills in total, the total value would be 200000 yen if all the bills were 10000-yen bills, and would be at most 195000 yen otherwise, so it would never be 196000 yen.

Sample Input 3

1000 1234000

Sample Output 3

14 27 959

There are also many other possibilities.

Sample Input 4

2000 20000000

Sample Output 4

2000 0 0

Problem Statement

You are given a string S consisting of lowercase English letters. Another string T is initially empty. Determine whether it is possible to obtain S = T by performing the following operation an arbitrary number of times:

• Append one of the following at the end of T: dream, dreamer, erase and eraser.

Constraints

• 1≦|S|≦10^5
• S consists of lowercase English letters.

Sample Input 1

erasedream

Sample Output 1

YES

Append erase and dream at the end of T in this order, to obtain S = T.

Sample Input 2

dreameraser

Sample Output 2

YES

Append dream and eraser at the end of T in this order, to obtain S = T.

Sample Input 3

dreamerer

Sample Output 3

NO

Problem Statement

AtCoDeer the deer is going on a trip in a two-dimensional plane. In his plan, he will depart from point (0, 0) at time 0, then for each i between 1 and N (inclusive), he will visit point (x_i,y_i) at time t_i.

If AtCoDeer is at point (x, y) at time t, he can be at one of the following points at time t+1: (x+1,y), (x-1,y), (x,y+1) and (x,y-1). Note that he cannot stay at his place. Determine whether he can carry out his plan.

Constraints

• 1 ≤ N ≤ 10^5
• 0 ≤ x_i ≤ 10^5
• 0 ≤ y_i ≤ 10^5
• 1 ≤ t_i ≤ 10^5
• t_i < t_{i+1} (1 ≤ i ≤ N-1)
• All input values are integers.

Sample Input 1

2
3 1 2
6 1 1

Sample Output 1

Yes

For example, he can travel as follows: (0,0), (0,1), (1,1), (1,2), (1,1), (1,0), then (1,1).

Sample Input 2

1
2 100 100

Sample Output 2

No

It is impossible to be at (100,100) two seconds after being at (0,0).

Sample Input 3

2
5 1 1
100 1 1

Sample Output 3

No

Problem Statement

This is an interactive task. Please note that these are not beginner questions.

If you are a beginner, try the AtCoder Beginners Selection!

There are N balls labeled with the first N uppercase letters. The balls have pairwise distinct weights.

You are allowed to ask at most Q queries. In each query, you can compare the weights of two balls (see Input/Output section for details).

Sort the balls in the ascending order of their weights.

Constraints

• (N, Q) = (26, 1000), (26, 100), or (5, 7).

Partial Score

There are three testsets. Each testset is worth 100 points.

• In testset 1, N = 26 and Q = 1000.
• In testset 2, N = 26 and Q = 100.
• In testset 3, N = 5 and Q = 7.

Input and Output

First, you are given N and Q from Standard Input in the following format:

N Q

Then, you start asking queries (at most Q times). Each query must be printed to Standard Output in the following format:

? c_1 c_2

Here each of c_1 and c_2 must be one of the first N uppercase letters, and c_1 and c_2 must be distinct.

Then, you are given the answer to the query from Standard Input in the following format:

ans

Here ans is either < or >. When ans is <, the ball c_2 is heavier than the ball c_1, and otherwise the ball c_1 is heavier than the ball c_2.

Finally, you must print the answer to Standard Output in the following format:

! ans

Here ans must be a string of length N, and it must contain each of the first N uppercase letters once. It must represent the weights of the balls in the ascending order.

Judgement

• After each output, you must flush Standard Output. Otherwise you may get TLE.
• After you print the answer, the program must be terminated immediately. Otherwise, the behavior of the judge is undefined.
• When your output is invalid or incorrect, the behavior of the judge is undefined (it does not necessarily give WA).

Sample Code

Here is a sample solution for 100 points. The code is obtainable for partial points, so submitting it will result in a WA.

#include <cstdio>
#include <string>

using namespace std;

int main(void){
  int N,Q,i,j;

  scanf("%d%d", &N, &Q);

  string s;
  for(i=0;i<N;i++) s += (char)('A' + i);

  for(i=0;i<N;i++) for(j=0;j<N-1;j++){
    printf("? %c %c\n", s[j], s[j+1]);
    fflush(stdout);
    char ans;
    scanf(" %c", &ans);
    if(ans == '>') swap(s[j], s[j+1]);
  }

  printf("! %s\n", s.c_str());
  fflush(stdout);

  return 0;
}

Sample

In this sample N = 3, Q = 10, and the answer is BAC.