Problem Statement

Takahashi is developing an RPG. He has decided to write a code that checks whether two maps are equal.

We have grids A and B with H horizontal rows and W vertical columns. Each cell in the grid has a symbol # or . written on it.
The symbols written on the cell at the i-th row from the top and j-th column from the left in A and B are denoted by A_{i, j} and B_{i, j}, respectively.

The following two operations are called a vertical shift and horizontal shift.

• For each j=1, 2, \dots, W, simultaneously do the following:
  • simultaneously replace A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} with A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j}.
• For each i = 1, 2, \dots, H, simultaneously do the following:
  • simultaneously replace A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} with A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1}.

Is there a pair of non-negative integers (s, t) that satisfies the following condition? Print Yes if there is, and No otherwise.

• After applying a vertical shift s times and a horizontal shift t times, A is equal to B.

Here, A is said to be equal to B if and only if A_{i, j} = B_{i, j} for all integer pairs (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W.

Constraints

• 2 \leq H, W \leq 30
• A_{i,j} is # or ., and so is B_{i,j}.
• H and W are integers.

Sample Input 1

4 3
..#
...
.#.
...
#..
...
.#.
...

Sample Output 1

Yes

By choosing (s, t) = (2, 1), the resulting A is equal to B.
We describe the procedure when (s, t) = (2, 1) is chosen. Initially, A is as follows.

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

We first apply a vertical shift to make A as follows.

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

Then we apply another vertical shift to make A as follows.

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

Finally, we apply a horizontal shift to make A as follows, which equals B.

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

Sample Input 2

3 2
##
##
#.
..
#.
#.

Sample Output 2

No

No choice of (s, t) makes A equal B.

Sample Input 3

4 5
#####
.#...
.##..
..##.
...##
#...#
#####
...#.

Sample Output 3

Yes

Sample Input 4

10 30
..........##########..........
..........####....###.....##..
.....##....##......##...#####.
....####...##..#####...##...##
...##..##..##......##..##....#
#.##....##....##...##..##.....
..##....##.##..#####...##...##
..###..###..............##.##.
.#..####..#..............###..
#..........##.................
................#..........##.
######....................####
....###.....##............####
.....##...#####......##....##.
.#####...##...##....####...##.
.....##..##....#...##..##..##.
##...##..##.....#.##....##....
.#####...##...##..##....##.##.
..........##.##...###..###....
...........###...#..####..#...

Sample Output 4

Yes

Problem Statement

You are given a string S. Find the lexicographically smallest string S' obtained by permuting the characters of S.

Here, for different two strings s = s_1 s_2 \ldots s_n and t = t_1 t_2 \ldots t_m, s \lt t holds lexicographically when one of the conditions below is satisfied.

• There is an integer i\ (1 \leq i \leq \min(n,m)) such that s_i \lt t_i and s_j=t_j for all integers j\ (1 \leq j \lt i).
• s_i = t_i for all integers i\ (1 \leq i \leq \min(n,m)), and n \lt m.

Constraints

• S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

aba

Sample Output 1

aab

Three strings can be obtained by permuting aba:

• aba
• aab
• baa

The lexicographically smallest among them is aab.

Sample Input 2

zzzz

Sample Output 2

zzzz

Problem Statement

You are given a positive integer N.

Find the maximum value of a palindromic cube number not greater than N.

Here, a positive integer K is defined to be a palindromic cube number if and only if it satisfies the following two conditions:

• There is a positive integer x such that x^3 = K.
• The decimal representation of K without leading zeros is a palindrome. More precisely, if K is represented as K = \sum_{i = 0}^{L-1} A_i10^i using integers A_0, A_1, \ldots, A_{L-2} between 0 and 9, inclusive, and an integer A_{L-1} between 1 and 9, inclusive, then A_i = A_{L-1-i} for all i = 0, 1, \ldots, L-1.

Constraints

• N is a positive integer not greater than 10^{18}.

Sample Input 1

345

Sample Output 1

343

343 is a palindromic cube number, while 344 and 345 are not. Thus, the answer is 343.

Sample Input 2

6

Sample Output 2

1

Sample Input 3

123456789012345

Sample Output 3

1334996994331

Problem Statement

A positive integer x is called a 321-like Number when it satisfies the following condition. This definition is the same as the one in Problem A.

• The digits of x are strictly decreasing from top to bottom.
• In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
  • (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

Find the K-th smallest 321-like Number.

Constraints

• All input values are integers.
• 1 \le K
• At least K 321-like Numbers exist.

Sample Input 1

15

Sample Output 1

32

The 321-like Numbers are (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) from smallest to largest.
The 15-th smallest of them is 32.

Sample Input 2

321

Sample Output 2

9610

Sample Input 3

777

Sample Output 3

983210

Problem Statement

There are N trampolines on a two-dimensional planar town where Takahashi lives. The i-th trampoline is located at the point (x_i, y_i) and has a power of P_i. Takahashi's jumping ability is denoted by S. Initially, S=0. Every time Takahashi trains, S increases by 1.

Takahashi can jump from the i-th to the j-th trampoline if and only if:

• P_iS\geq |x_i - x_j| +|y_i - y_j|.

Takahashi's objective is to become able to choose a starting trampoline such that he can reach any trampoline from the chosen one with some jumps.

At least how many times does he need to train to achieve his objective?

Constraints

• 2 \leq N \leq 200
• -10^9 \leq x_i,y_i \leq 10^9
• 1 \leq P_i \leq 10^9
• (x_i, y_i) \neq (x_j,y_j)\ (i\neq j)
• All values in input are integers.

Sample Input 1

4
-10 0 1
0 0 5
10 0 1
11 0 1

Sample Output 1

2

If he trains twice, S=2, in which case he can reach any trampoline from the 2-nd one.

For example, he can reach the 4-th trampoline as follows.

• Jump from the 2-nd to the 3-rd trampoline. (Since P_2 S = 10 and |x_2-x_3| + |y_2-y_3| = 10, it holds that P_2 S \geq |x_2-x_3| + |y_2-y_3|.)

• Jump from the 3-rd to the 4-th trampoline. (Since P_3 S = 2 and |x_3-x_4| + |y_3-y_4| = 1, it holds that P_3 S \geq |x_3-x_4| + |y_3-y_4|.)

Sample Input 2

7
20 31 1
13 4 3
-10 -15 2
34 26 5
-2 39 4
0 -50 1
5 -20 2

Sample Output 2

18