Problem Statement

Determine if there is a segment that directly connects the points numbered a and b in the figure below.

Constraints

• 1 \leq a \lt b \leq 15
• a and b are integers.

Sample Input 1

1 2

Sample Output 1

Yes

In the figure in the Problem Statement, there is a segment that directly connects the points numbered 1 and 2, so Yes should be printed.

Sample Input 2

2 8

Sample Output 2

No

In the figure in the Problem Statement, there is no segment that directly connects the points numbered 2 and 8, so No should be printed.

Sample Input 3

14 15

Sample Output 3

No

Problem Statement

You are given a string S of length N consisting of lowercase English letters. The x-th (1 \le x \le N) character of S is S_x.

For each i=1,2,\dots,N-1, find the maximum non-negative integer l that satisfies all of the following conditions:

• l+i \le N, and
• for all integers k such that 1 \le k \le l, it holds that S_{k} \neq S_{k+i}.

Note that l=0 always satisfies the conditions.

Constraints

• N is an integer such that 2 \le N \le 5000.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

6
abcbac

Sample Output 1

5
1
2
0
1

In this input, S= abcbac.

• When i=1, we have S_1 \neq S_2, S_2 \neq S_3, \dots, and S_5 \neq S_6, so the maximum value is l=5.
• When i=2, we have S_1 \neq S_3 but S_2 = S_4, so the maximum value is l=1.
• When i=3, we have S_1 \neq S_4 and S_2 \neq S_5 but S_3 = S_6, so the maximum value is l=2.
• When i=4, we have S_1 = S_5, so the maximum value is l=0.
• When i=5, we have S_1 \neq S_6, so the maximum value is l=1.

Problem Statement

In a parallel universe, AtCoder holds AtCoder Big Contest, where 10^{16} problems are given at once.
The IDs of the problems are as follows, from the 1-st problem in order: A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...

In other words, the IDs are given in the following order:

• the strings of length 1 consisting of uppercase English letters, in lexicographical order;
• the strings of length 2 consisting of uppercase English letters, in lexicographical order;
• the strings of length 3 consisting of uppercase English letters, in lexicographical order;
• ...

Given a string S that is an ID of a problem given in this contest, find the index of the problem. (See also Samples.)

Constraints

• S is a valid ID of a problem given in AtCoder Big Contest.

Sample Input 1

AB

Sample Output 1

28

The problem whose ID is AB is the 28-th problem of AtCoder Big Contest, so 28 should be printed.

Sample Input 2

C

Sample Output 2

3

The problem whose ID is C is the 3-rd problem of AtCoder Big Contest, so 3 should be printed.

Sample Input 3

BRUTMHYHIIZP

Sample Output 3

10000000000000000

The problem whose ID is BRUTMHYHIIZP is the 10^{16}-th (last) problem of AtCoder Big Contest, so 10^{16} should be printed as an integer.

Problem Statement

You run a web service with N users.

The i-th user with a current handle S_i wants to change it to T_i.
Here, S_1,\ldots, and S_N are pairwise distinct, and so are T_1,\ldots, and T_N.

Determine if there is an appropriate order to change their handles to fulfill all of their requests subject to the following conditions:

• you change only one user's handle at a time;
• you change each user's handle only once;
• when changing the handle, the new handle should not be used by other users at that point.

Constraints

• 1 \leq N \leq 10^5
• S_i and T_i are strings of length between 1 and 8 (inclusive) consisting of lowercase English letters.
• S_i \neq T_i
• S_i are pairwise distinct.
• T_i are pairwise distinct.

Sample Input 1

2
b m
m d

Sample Output 1

Yes

The 1-st user with a current handle b wants to change it to m.
The 2-nd user with a current handle m wants to change it to d.

First, you change the 2-nd user's handle from m to d; then you change the 1-st user's handle from b to m. This way, you can achieve the objective.

Note that you cannot change the 1-st user's handle to m at first, because it is used by the 2-nd user at that point.

Sample Input 2

3
a b
b c
c a

Sample Output 2

No

The 1-st user with a current handle a wants to change it to b.
The 2-nd user with a current handle b wants to change it to c.
The 3-rd user with a current handle c wants to change it to a.

We cannot change their handles subject to the conditions.

Sample Input 3

5
aaa bbb
yyy zzz
ccc ddd
xxx yyy
bbb ccc

Sample Output 3

Yes

Problem Statement

In the world where Takahashi lives, a week has N days.

Takahashi, the king of the Kingdom of AtCoder, assigns "weekday" or "holiday" to each day of week. The assignments should be the same for all weeks. At least one day of week should be assigned "holiday".

Under such conditions, the productivity of the i-th day of week is defined by a sequence A of length N as follows:

• if the i-th day of week is "holiday", its productivity is 0;
• if the i-th day of week is "weekday", its productivity is A_{\min(x,y)}, if the last holiday is x days before and the next one is y days after.
  • Note that the last/next holiday may belong to a different week due to the periodic assignments. For details, see the Samples.

Find the maximum productivity per week when the assignments are chosen optimally.
Here, the productivity per week refers to the sum of the productivities of the 1-st, 2-nd, \dots, and N-th day of week.

Constraints

• All values in the input are integers.
• 1 \le N \le 5000
• 1 \le A_i \le 10^9

Sample Input 1

7
10 10 1 1 1 1 1

Sample Output 1

50

For example, we can assign "holiday" to the 2-nd and 4-th day of week and "weekday" to the rest to achieve a productivity of 50 per week:

• the 1-st day of week ... x=4 and y=1, so its productivity is A_1 = 10.
• the 2-nd day of week ... it is holiday, so its productivity is 0.
• the 3-st day of week ... x=1 and y=1, so its productivity is A_1 = 10.
• the 4-th day of week ... it is holiday, so its productivity is 0.
• the 5-th day of week ... x=1 and y=4, so its productivity is A_1 = 10.
• the 6-th day of week ... x=2 and y=3, so its productivity is A_2 = 10.
• the 7-th day of week ... x=3 and y=2, so its productivity is A_2 = 10.

It is impossible to make the productivity per week 51 or greater.

Sample Input 2

10
200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20

Sample Output 2

5100000000

Sample Input 3

20
38 7719 21238 2437 8855 11797 8365 32285 10450 30612 5853 28100 1142 281 20537 15921 8945 26285 2997 14680

Sample Output 3

236980

Problem Statement

You are given a string S of length N consisting of lowercase English letters, and Q queries. Process the queries in order.

Each query is of one of the following two kinds:

• 1 x c : replace the x-th character of S by the character c.
• 2 l r : let T be the string obtained by sorting the characters of S in ascending order. Print Yes if the string consisting of the l-th through r-th characters of S is a substring of T; print No otherwise.

Constraints

• 1\leq N \leq 10^5
• S is a string of length N consisting of lowercase English letters.
• 1 \leq Q \leq 10^5
• For each query of the first kind, 1 \leq x \leq N.
• For each query of the first kind, c is a lowercase English letter.
• For each query of the second kind, 1 \leq l \leq r \leq N.

Sample Input 1

6
abcdcf
4
2 1 3
2 2 6
1 5 e
2 2 6

Sample Output 1

Yes
No
Yes

• In the 1-st query, abccdf is the string T obtained by sorting the characters of S in ascending order. The string abc, consisting of the 1-st through 3-rd characters of S, is a substring of T, so Yes should be printed.
• In the 2-nd query, abccdf is the string T obtained by sorting the characters of S in ascending order. The string bcdcf, consisting of the 2-nd through 6-th characters of S, is not a substring of T, so No should be printed.
• The 3-rd query sets the 5-th character of S to e, making S abcdef.
• In the 4-th query, abcdef is the string T obtained by sorting the characters of S in ascending order. The string bcdef, consisting of the 2-nd through 6-th characters of S, is a substring of T, so Yes should be printed.

Problem Statement

We have a grid with H horizontal rows and W vertical columns. We denote by square (i,j) the square at the i-th row from the top and j-th column from the left.

We want to cover this grid with 1 \times 1 tiles and 1 \times 2 tiles so that no tiles overlap and everywhere is covered by a tile. (A tile can be rotated.)

Each square has 1, 2, or ? written on it. The character written on square (i, j) is c_{i,j}.
A square with 1 written on it must be covered by a 1 \times 1 tile, and a square with 2 by a 1 \times 2 tile. A square with ? may be covered by any kind of tile.

Determine if there is such a placement of tiles.

Constraints

• 1 \leq H,W \leq 300
• H and W are integers.
• c_{i,j} is one of 1, 2, and ?.

Sample Input 1

3 4
2221
?1??
2?21

Sample Output 1

Yes

For example, the following placement satisfies the conditions.

Sample Input 2

3 4
2?21
??1?
2?21

Sample Output 2

No

There is no placement that satisfies the conditions.

Sample Input 3

5 5
11111
11111
11211
11111
11111

Sample Output 3

No

Problem Statement

You are given integers N and K, and a sequence E of length K.
Find the number, modulo \color{red}{10^9+7}, of sequences of length N consisting of positive integers that satisfy the following conditions:

• no element is a square number;
• the product of all elements is \displaystyle \prod_{i=1}^{K} p_i^{E_i}.

Here,

• p_i denotes the i-th smallest prime.
• Two sequences A and B of the same length consisting of positive integers are considered different if and only if there exists an integer i such that the i-th terms of A and B are different.

Constraints

• All values in the input are integers.
• 1 \le N,K,E_i \le 10000

Sample Input 1

3 2
3 2

Sample Output 1

15

The sequences of length 3 whose total product is 72=2^3 \times 3^2 are listed below.

• (1,1,72) and its permutations (3 instances) are inappropriate because 1 is a square number.
• (1,2,36) and its permutations (6 instances) are inappropriate because 1 and 36 are square numbers.
• (1,3,24) and its permutations (6 instances) are inappropriate because 1 is a square number.
• (1,4,18) and its permutations (6 instances) are inappropriate because 1 and 4 are square numbers.
• (1,6,12) and its permutations (6 instances) are inappropriate because 1 is a square number.
• (1,8,9) and its permutations (6 instances) are inappropriate because 1 and 9 are square numbers.
• (2,2,18) and its permutations (3 instances) are appropriate.
• (2,3,12) and its permutations (6 instances) are appropriate.
• (2,4,9) and its permutations (6 instances) are inappropriate because 4 and 9 are square numbers.
• (2,6,6) and its permutations (3 instances) are appropriate.
• (3,3,8) and its permutations (3 instances) are appropriate.
• (3,4,6) and its permutations (6 instances) are inappropriate because 4 is a square number.

Therefore, 15 sequences satisfy the conditions.

Sample Input 2

285 10
3141 5926 5358 9793 2384 6264 3383 279 5028 8419

Sample Output 2

672860525

Be sure to find the count modulo \color{red}{10^9+7}.