Problem Statement

There are N sticks with several balls stuck onto them. Each ball has a lowercase English letter written on it.

For each i = 1, 2, \ldots, N, the letters written on the balls stuck onto the i-th stick are represented by a string S_i. Specifically, the number of balls stuck onto the i-th stick is the length |S_i| of the string S_i, and S_i is the sequence of letters on the balls starting from one end of the stick.

Two sticks are considered the same when the sequence of letters on the balls starting from one end of one stick is equal to the sequence of letters starting from one end of the other stick. More formally, for integers i and j between 1 and N, inclusive, the i-th and j-th sticks are considered the same if and only if S_i equals S_j or its reversal.

Print the number of different sticks among the N sticks.

Constraints

• N is an integer.
• 2 \leq N \leq 2 \times 10^5
• S_i is a string consisting of lowercase English letters.
• |S_i| \geq 1
• \sum_{i = 1}^N |S_i| \leq 2 \times 10^5

Sample Input 1

6
a
abc
de
cba
de
abc

Sample Output 1

3

• S_2 = abc equals the reversal of S_4 = cba, so the second and fourth sticks are considered the same.
• S_2 = abc equals S_6 = abc, so the second and sixth sticks are considered the same.
• S_3 = de equals S_5 = de, so the third and fifth sticks are considered the same.

Therefore, there are three different sticks among the six: the first, second (same as the fourth and sixth), and third (same as the fifth).

Problem Statement

There is a slot machine with N reels.
The placement of symbols on the i-th reel is represented by a string S_i of length 10 containing each of 0, 1, \ldots, 9 exactly once.

Each reel has a corresponding button. For each non-negative integer t, Takahashi can press one of the buttons of his choice (or do nothing) t seconds after the reels start spinning.
If the button for the i-th reel is pressed t seconds after the start of the spin, the i-th reel will stop to display the ((t\bmod{10})+1)-th character of S_i.
Here, t\bmod{10} denotes the remainder when t is divided by 10.

Takahashi wants to stop all reels to make them display the same character.
Find the minimum number of seconds needed to achieve his objective after the start of the spin.

Constraints

• 2\leq N\leq 100
• N is an integer.
• S_i is a string of length 10 containing each of 0, 1, \ldots, 9 exactly once.

Sample Input 1

3
1937458062
8124690357
2385760149

Sample Output 1

6

Takahashi can make all reels display 8 in 6 seconds after the start of the spin by stopping them as follows.

• 0 seconds after the start of the spin, press the button for the 2-nd reel, making it stop to display the ((0\bmod{10})+1=1)-st character of S_2, 8.
• 2 seconds after the start of the spin, press the button for the 3-rd reel, making it stop to display the ((2\bmod{10})+1=3)-rd character of S_3, 8.
• 6 seconds after the start of the spin, press the button for the 1-st reel, making it stop to display the ((6\bmod{10})+1=7)-th character of S_1, 8.

There is no way to make all reels display the same character in five seconds or less, so the answer is 6.

Sample Input 2

5
0123456789
0123456789
0123456789
0123456789
0123456789

Sample Output 2

40

Note that he must stop all reels to make them display the same character.

Problem Statement

You are given a tree with N vertices: vertex 1, vertex 2, \ldots, vertex N. The i-th edge (1\leq i\lt N) connects vertex u _ i and vertex v _ i.

Consider repeating the following operation some number of times:

• Choose one leaf vertex v and delete it along with all incident edges.

Find the minimum number of operations required to delete vertex 1.

Constraints

• 2\leq N\leq3\times10^5
• 1\leq u _ i\lt v _ i\leq N\ (1\leq i\lt N)
• The given graph is a tree.
• All input values are integers.

Sample Input 1

9
1 2
2 3
2 4
2 5
1 6
6 7
7 8
7 9

Sample Output 1

5

The given graph looks like this:

For example, you can choose vertices 9,8,7,6,1 in this order to delete vertex 1 in five operations.

Vertex 1 cannot be deleted in four or fewer operations, so print 5.

Sample Input 2

6
1 2
2 3
2 4
3 5
3 6

Sample Output 2

1

In the given graph, vertex 1 is a leaf. Hence, you can choose and delete vertex 1 in the first operation.

Sample Input 3

24
3 6
7 17
7 20
7 11
14 18
17 21
6 19
5 22
9 24
11 14
6 23
8 17
9 12
4 17
2 15
1 17
3 9
10 16
7 13
2 16
1 16
5 7
1 3

Sample Output 3

12

Problem Statement

This is an interactive problem (where your program interacts with the judge via input and output).

You are given a positive integer N and integers L and R such that 0 \leq L \leq R < 2^N. The judge has a hidden sequence A = (A_0, A_1, \dots, A_{2^N-1}) consisting of integers between 0 and 99, inclusive.

Your goal is to find the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100. However, you cannot directly know the values of the elements in the sequence A. Instead, you can ask the judge the following question:

• Choose non-negative integers i and j such that 2^i(j+1) \leq 2^N. Let l = 2^i j and r = 2^i (j+1) - 1. Ask for the remainder when A_l + A_{l+1} + \dots + A_r is divided by 100.

Let m be the minimum number of questions required to determine the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100 for any sequence A. You need to find this remainder within m questions.

Constraints

• 1 \leq N \leq 18
• 0 \leq L \leq R \leq 2^N - 1
• All input values are integers.

Input and Output

This is an interactive problem (where your program interacts with the judge via input and output).

First, read the integers N, L, and R from Standard Input:

N L R

Then, repeat asking questions until you can determine the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100. Each question should be printed in the following format:

? i j

Here, i and j must satisfy the following constraints:

• i and j are non-negative integers.
• 2^i(j+1) \leq 2^N

The response to the question will be given in the following format from Standard Input:

T

Here, T is the answer to the question, which is the remainder when A_l + A_{l+1} + \dots + A_r is divided by 100, where l = 2^i j and r = 2^i (j+1) - 1.

If i and j do not satisfy the constraints, or if the number of questions exceeds m, then T will be -1.

If the judge returns -1, your program is already considered incorrect. In this case, terminate the program immediately.

Once you have determined the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100, print the remainder S in the following format and terminate the program immediately:

! S

Notes

• At the end of each output, print a newline and flush Standard Output. Otherwise, the verdict may be TLE.
• If your output is malformed or your program exits prematurely, the verdict will be indeterminate.
• After printing the answer, terminate the program immediately. Otherwise, the verdict will be indeterminate.

Example

Here is an example for N=3, L=1, R=5, and A=(31, 41, 59, 26, 53, 58, 97, 93). In this case, m=3, so you can ask up to three questions.

Problem Statement

We have N cards. The i-th card has a string S_i written on it.

Find the lexicographically smallest string that can be obtained by choosing K of these cards and concatenating them in any order.

Constraints

• 1 \leq K \leq N \leq 50
• 1 \leq |S_i| \leq 50
• S_i consists of lowercase English letters.

Sample Input 1

4 3
ode
zaaa
r
atc

Sample Output 1

atcoder

Note that it is not possible to reverse or permute the string written on a card.
For example, ode written on the first card cannot be used as edo or deo.

Sample Input 2

5 2
z
z
zzz
z
zzzzzz

Sample Output 2

zz

There may be a pair i, j (i\neq j) such that S_i = S_j.