Problem Statement

Takahashi is growing a plant. Its height at the time of germination is 0\,\mathrm{cm}. Considering the day of germination as day 0, its height increases by 2^i\,\mathrm{cm} day i's night (0 \le i).

Takahashi's height is H\,\mathrm{cm}.

Every morning, Takahashi measures his height against this plant. Find the first day such that the plant's height is strictly greater than Takahashi's height in the morning.

Constraints

• 1 \leq H \leq 10^{9}
• All input values are integers.

Sample Input 1

54

Sample Output 1

6

The plant's height in the mornings of days 1, 2, 3, 4, 5, 6 will be 1\,\mathrm{cm}, 3\,\mathrm{cm}, 7\,\mathrm{cm}, 15\,\mathrm{cm}, 31\,\mathrm{cm}, 63\,\mathrm{cm}, respectively. The plant becomes taller than Takahashi in the morning day 6, so print 6.

Sample Input 2

7

Sample Output 2

4

The plant's height will be 7\,\mathrm{cm} in the morning of day 3 and 15\,\mathrm{cm} in the morning day 4. The plant becomes taller than Takahashi in the morning of day 4, so print 4. Note that, in the morning of day 3, the plant is as tall as Takahashi, but not taller.

Sample Input 3

262144

Sample Output 3

19

Problem Statement

There are 12 strings S_1, S_2, \ldots, S_{12} consisting of lowercase English letters.

Find how many integers i (1 \leq i \leq 12) satisfy that the length of S_i is i.

Constraints

• Each S_i is a string of length between 1 and 100, inclusive, consisting of lowercase English letters. (1 \leq i \leq 12)

Sample Input 1

january
february
march
april
may
june
july
august
september
october
november
december

Sample Output 1

1

There is only one integer i such that the length of S_i is i: 9. Thus, print 1.

Sample Input 2

ve
inrtfa
npccxva
djiq
lmbkktngaovl
mlfiv
fmbvcmuxuwggfq
qgmtwxmb
jii
ts
bfxrvs
eqvy

Sample Output 2

2

There are two integers i such that the length of S_i is i: 4 and 8. Thus, print 2.

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

Cell (i, j) is empty if C_{i, j} is ., and not empty if C_{i, j} is #.

Takahashi is currently at cell (S_i, S_j), and he will act according to the following rules for i = 1, 2, \ldots, |X| in order.

• If the i-th character of X is L, and the cell to the left of his current cell exists and is empty, he moves to the cell to the left. Otherwise, he stays in the current cell.
• If the i-th character of X is R, and the cell to the right of his current cell exists and is empty, he moves to the cell to the right. Otherwise, he stays in the current cell.
• If the i-th character of X is U, and the cell above his current cell exists and is empty, he moves to the cell above. Otherwise, he stays in the current cell.
• If the i-th character of X is D, and the cell below his current cell exists and is empty, he moves to the cell below. Otherwise, he stays in the current cell.

Print the cell where he is after completing the series of actions.

Constraints

• 1 \leq H, W \leq 50
• 1 \leq S_i \leq H
• 1 \leq S_j \leq W
• H, W, S_i, S_j are integers.
• C_{i, j} is . or #.
• C_{S_i, S_j} = .
• X is a string of length between 1 and 50, inclusive, consisting of L, R, U, D.

Sample Input 1

2 3
2 1
.#.
...
ULDRU

Sample Output 1

2 2

Takahashi starts at cell (2, 1). His series of actions are as follows:

• The 1st character of X is U, and the cell above (2, 1) exists and is an empty cell, so he moves to the cell above, which is (1, 1).
• The 2nd character of X is L, and the cell to the left of (1, 1) does not exist, so he stays at (1, 1).
• The 3rd character of X is D, and the cell below (1, 1) exists and is an empty cell, so he moves to the cell below, which is (2, 1).
• The 4th character of X is R, and the cell to the right of (2, 1) exists and is an empty cell, so he moves to the cell to the right, which is (2, 2).
• The 5th character of X is U, and the cell above (2, 2) exists but is not an empty cell, so he stays at (2, 2).

Therefore, after completing the series of actions, he is at cell (2, 2).

Sample Input 2

4 4
4 2
....
.#..
...#
....
DUUUURULRD

Sample Output 2

2 4

Sample Input 3

6 6
1 1
.#####
######
######
######
######
######
RURLDLULLRULRDL

Sample Output 3

1 1

Problem Statement

You are given N sequences numbered 1 to N.
Sequence i has a length of L_i and its j-th element (1 \leq j \leq L_i) is a_{i,j}.

Sequence i and Sequence j are considered the same when L_i = L_j and a_{i,k} = a_{j,k} for every k (1 \leq k \leq L_i).
How many different sequences are there among Sequence 1 through Sequence N?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
• 0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
• The total number of elements in the sequences, \sum_{i=1}^N L_i, does not exceed 2 \times 10^5.
• All values in input are integers.

Sample Input 1

4
2 1 2
2 1 1
2 2 1
2 1 2

Sample Output 1

3

Sample Input 1 contains four sequences:

• Sequence 1 : (1, 2)
• Sequence 2 : (1, 1)
• Sequence 3 : (2, 1)
• Sequence 4 : (1, 2)

Except that Sequence 1 and Sequence 4 are the same, these sequences are pairwise different, so we have three different sequences.

Sample Input 2

5
1 1
1 1
1 2
2 1 1
3 1 1 1

Sample Output 2

4

Sample Input 2 contains five sequences:

• Sequence 1 : (1)
• Sequence 2 : (1)
• Sequence 3 : (2)
• Sequence 4 : (1, 1)
• Sequence 5 : (1, 1, 1)

Sample Input 3

1
1 1

Sample Output 3

1

Problem Statement

There is a two-dimensional plane. For integers r and c between 1 and 9, there is a pawn at the coordinates (r,c) if the c-th character of S_{r} is #, and nothing if the c-th character of S_{r} is ..

Find the number of squares in this plane with pawns placed at all four vertices.

Constraints

• Each of S_1,\ldots,S_9 is a string of length 9 consisting of # and ..

Sample Input 1

##.......
##.......
.........
.......#.
.....#...
........#
......#..
.........
.........

Sample Output 1

2

The square with vertices (1,1), (1,2), (2,2), and (2,1) have pawns placed at all four vertices.

The square with vertices (4,8), (5,6), (7,7), and (6,9) also have pawns placed at all four vertices.

Thus, the answer is 2.

Sample Input 2

.#.......
#.#......
.#.......
.........
....#.#.#
.........
....#.#.#
........#
.........

Sample Output 2

3