Problem Statement

For a non-negative integer K, we define a level-K carpet as follows:

• A level-0 carpet is a 1 \times 1 grid consisting of a single black cell.
• For K > 0, a level-K carpet is a 3^K \times 3^K grid. When this grid is divided into nine 3^{K-1} \times 3^{K-1} blocks:
  • The central block consists entirely of white cells.
  • The other eight blocks are level-(K-1) carpets.

You are given a non-negative integer N.
Print a level-N carpet according to the specified format.

Constraints

• 0 \leq N \leq 6
• N is an integer.

Sample Input 1

1

Sample Output 1

###
#.#
###

A level-1 carpet is a 3 \times 3 grid as follows:

When output according to the specified format, it looks like the sample output.

Sample Input 2

2

Sample Output 2

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

A level-2 carpet is a 9 \times 9 grid.

Problem Statement

The coordinate plane is covered with 2\times1 tiles. The tiles are laid out according to the following rules:

• For an integer pair (i,j), the square A _ {i,j}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace is contained in one tile.
• When i+j is even, A _ {i,j} and A _ {i + 1,j} are contained in the same tile.

Tiles include their boundaries, and no two different tiles share a positive area.

Near the origin, the tiles are laid out as follows:

Takahashi starts at the point (S _ x+0.5,S _ y+0.5) on the coordinate plane.

He can repeat the following move as many times as he likes:

• Choose a direction (up, down, left, or right) and a positive integer n. Move n units in that direction.

Each time he enters a tile, he pays a toll of 1.

Find the minimum toll he must pay to reach the point (T _ x+0.5,T _ y+0.5).

Constraints

• 0\leq S _ x\leq2\times10 ^ {16}
• 0\leq S _ y\leq2\times10 ^ {16}
• 0\leq T _ x\leq2\times10 ^ {16}
• 0\leq T _ y\leq2\times10 ^ {16}
• All input values are integers.

Sample Input 1

5 0
2 5

Sample Output 1

5

For example, Takahashi can pay a toll of 5 by moving as follows:

• Move left by 1. Pay a toll of 0.
• Move up by 1. Pay a toll of 1.
• Move left by 1. Pay a toll of 0.
• Move up by 3. Pay a toll of 3.
• Move left by 1. Pay a toll of 0.
• Move up by 1. Pay a toll of 1.

It is impossible to reduce the toll to 4 or less, so print 5.

Sample Input 2

3 1
4 1

Sample Output 2

0

There are cases where no toll needs to be paid.

Sample Input 3

2552608206527595 5411232866732612
771856005518028 7206210729152763

Sample Output 3

1794977862420151

Note that the value to be output may exceed the range of a 32-bit integer.

Problem Statement

You initially have an empty string S.
Additionally, there are bags 1, 2, \dots, N, each containing some strings.
Bag i contains A_i strings S_{i,1}, S_{i,2}, \dots, S_{i,A_i}.

You will repeat the following steps for i = 1, 2, \dots, N:

• Choose and perform one of the following two actions:
  • Pay 1 yen, select exactly one string from bag i, and concatenate it to the end of S.
  • Do nothing.

Given a string T, find the minimum amount of money required to make the final S equal T.
If there is no way to make the final S equal T, print -1.

Constraints

• T is a string consisting of lowercase English letters with length between 1 and 100, inclusive.
• N is an integer between 1 and 100, inclusive.
• A_i is an integer between 1 and 10, inclusive.
• S_{i,j} is a string consisting of lowercase English letters with length between 1 and 10, inclusive.

Sample Input 1

abcde
3
3 ab abc abcd
4 f c cd bcde
2 e de

Sample Output 1

2

For example, doing the following makes the final S equal T with two yen, which can be shown to be the minimum amount required.

• For i=1, select abc from bag 1 and concatenate it to the end of S, making S= abc.
• For i=2, do nothing.
• For i=3, select de from bag 3 and concatenate it to the end of S, making S= abcde.

Sample Input 2

abcde
3
2 ab abc
3 f c bcde
1 e

Sample Output 2

-1

There is no way to make the final S equal T, so print -1.

Sample Input 3

aaabbbbcccc
6
2 aa aaa
2 dd ddd
2 ab aabb
4 bbaa bbbc bbb bbcc
2 cc bcc
3 ccc cccc ccccc

Sample Output 3

4

Problem Statement

There are infinitely many packs, each containing N cards. In each pack, the i-th card is rare with probability P_i percent. Whether each card is rare is independent of other cards being rare.

You will now open the packs one by one, and obtain all the cards in each opened pack. When you keep opening packs until you have obtained a total of at least X rare cards, find the expected number of packs you will open.

Constraints

• 1 \leq N \leq 5000
• 1 \leq X \leq 5000
• 1 \leq P_i \leq 100
• All input values are integers.

Sample Input 1

2 2
50 100

Sample Output 1

1.5000000000000000

The number of packs opened will be 1 with probability \frac{1}{2}, and 2 with probability \frac{1}{2}.

Sample Input 2

2 3
40 60

Sample Output 2

3.2475579530543811

Sample Input 3

6 3
10 33 33 10 100 10

Sample Output 3

1.8657859189536100

Problem Statement

You are given strings S and T of length N each, consisting of lowercase English letters.

For a string X and an integer i, let f(X,i) be the string obtained by performing on X the following operation i times:

• Remove the first character of X and append the same character to the end of X.

Find the number of integer pairs (i,j) satisfying 0 \le i,j \le N-1 such that f(S,i) is lexicographically smaller than or equal to f(T,j).

Constraints

• 1 \le N \le 2 \times 10^5
• S and T are strings of length N each, consisting of lowercase English letters.
• N is an integer.

Sample Input 1

3
adb
cab

Sample Output 1

4

There are 4 pairs of (i, j) satisfying the conditions: (0,0),(0,2),(2,0), and (2,2).

(i,j)=(1,2) does not satisfy the conditions because f(S,i)=dba and f(T,j)=bca.

Sample Input 2

10
wsiuhwijsl
pwqoketvun

Sample Output 2

56