Problem Statement

You are given a string S.

Takahashi can insert the character A at any position in this string any number of times.

Can he change S into AKIHABARA?

Constraints

• 1 \leq |S| \leq 50
• S consists of uppercase English letters.

Sample Input 1

KIHBR

Sample Output 1

YES

Insert one A at each of the four positions: the beginning, immediately after H, immediately after B and the end.

Sample Input 2

AKIBAHARA

Sample Output 2

NO

The correct spell is AKIHABARA.

Sample Input 3

AAKIAHBAARA

Sample Output 3

NO

Problem Statement

Snuke has a string S consisting of three kinds of letters: a, b and c.

He has a phobia for palindromes, and wants to permute the characters in S so that S will not contain a palindrome of length 2 or more as a substring. Determine whether this is possible.

Constraints

• 1 \leq |S| \leq 10^5
• S consists of a, b and c.

Sample Input 1

abac

Sample Output 1

YES

As it stands now, S contains a palindrome aba, but we can permute the characters to get acba, for example, that does not contain a palindrome of length 2 or more.

Sample Input 2

aba

Sample Output 2

NO

Sample Input 3

babacccabab

Sample Output 3

YES

Problem Statement

In CODE FESTIVAL XXXX, there are N+1 participants from all over the world, including Takahashi.

Takahashi checked and found that the time gap (defined below) between the local times in his city and the i-th person's city was D_i hours. The time gap between two cities is defined as follows. For two cities A and B, if the local time in city B is d o'clock at the moment when the local time in city A is 0 o'clock, then the time gap between these two cities is defined to be min(d,24-d) hours. Here, we are using 24-hour notation. That is, the local time in the i-th person's city is either d o'clock or 24-d o'clock at the moment when the local time in Takahashi's city is 0 o'clock, for example.

Then, for each pair of two people chosen from the N+1 people, he wrote out the time gap between their cities. Let the smallest time gap among them be s hours.

Find the maximum possible value of s.

Constraints

• 1 \leq N \leq 50
• 0 \leq D_i \leq 12
• All input values are integers.

Sample Input 1

3
7 12 8

Sample Output 1

4

For example, consider the situation where it is 7, 12 and 16 o'clock in each person's city at the moment when it is 0 o'clock in Takahashi's city. In this case, the time gap between the second and third persons' cities is 4 hours.

Sample Input 2

2
11 11

Sample Output 2

2

Sample Input 3

1
0

Sample Output 3

0

Note that Takahashi himself is also a participant.

Problem Statement

In the final of CODE FESTIVAL in some year, there are N participants. The height and power of Participant i is H_i and P_i, respectively.

Ringo is hosting a game of stacking zabuton (cushions).

The participants will line up in a row in some order, and they will in turn try to add zabuton to the stack of zabuton. Initially, the stack is empty. When it is Participant i's turn, if there are H_i or less zabuton already stacked, he/she will add exactly P_i zabuton to the stack. Otherwise, he/she will give up and do nothing.

Ringo wants to maximize the number of participants who can add zabuton to the stack. How many participants can add zabuton to the stack in the optimal order of participants?

Constraints

• 1 \leq N \leq 5000
• 0 \leq H_i \leq 10^9
• 1 \leq P_i \leq 10^9

Sample Input 1

3
0 2
1 3
3 4

Sample Output 1

2

When the participants line up in the same order as the input, Participants 1 and 3 will be able to add zabuton.

On the other hand, there is no order such that all three participants can add zabuton. Thus, the answer is 2.

Sample Input 2

3
2 4
3 1
4 1

Sample Output 2

3

When the participants line up in the order 2, 3, 1, all of them will be able to add zabuton.

Sample Input 3

10
1 3
8 4
8 3
9 1
6 4
2 3
4 2
9 2
8 3
0 1

Sample Output 3

5

Problem Statement

Ringo has a string S.

He can perform the following N kinds of operations any number of times in any order.

• Operation i: For each of the characters from the L_i-th through the R_i-th characters in S, replace it with its succeeding letter in the English alphabet. (That is, replace a with b, replace b with c and so on.) For z, we assume that its succeeding letter is a.

Ringo loves palindromes and wants to turn S into a palindrome. Determine whether this is possible.

Constraints

• 1 \leq |S| \leq 10^5
• S consists of lowercase English letters.
• 1 \leq N \leq 10^5
• 1 \leq L_i \leq R_i \leq |S|

Sample Input 1

bixzja
2
2 3
3 6

Sample Output 1

YES

For example, if we perform Operation 1, 2 and 1 in this order, S changes as bixzja → bjyzja → bjzakb → bkaakb and becomes a palindrome.

Sample Input 2

abc
1
2 2

Sample Output 2

NO

Sample Input 3

cassert
4
1 2
3 4
1 1
2 2

Sample Output 3

YES

Problem Statement

Select any integer N between 1000 and 2000 (inclusive), and any integer K not less than 1, then solve the problem below.

Problem

We have N sheets of paper. Write K integers on each of them to satisfy the following conditions:

• Each integer written must be between 1 and N (inclusive).
• The K integers written on the same sheet must be all different.
• Each of the integers between 1 and N must be written on exactly K sheets.
• For any two sheet, there is exactly one integer that appears on both.

Sample Output

3 2
1 2
2 3
3 1

This is an example of a solution for N = 3 and K = 2.

Note that this output will be judged as incorrect, since the constraint on N is not satisfied.

Problem Statement

Consider the following game:

• The game is played using a row of N squares and many stones.
• First, a_i stones are put in Square i\ (1 \leq i \leq N).
• A player can perform the following operation as many time as desired: "Select an integer i such that Square i contains exactly i stones. Remove all the stones from Square i, and add one stone to each of the i-1 squares from Square 1 to Square i-1."
• The final score of the player is the total number of the stones remaining in the squares.

For a sequence a of length N, let f(a) be the minimum score that can be obtained when the game is played on a.

Find the sum of f(a) over all sequences a of length N where each element is between 0 and K (inclusive). Since it can be extremely large, find the answer modulo 1000000007 (= 10^9+7).

Constraints

• 1 \leq N \leq 100
• 1 \leq K \leq N

Sample Input 1

2 2

Sample Output 1

10

There are nine sequences of length 2 where each element is between 0 and 2. For each of them, the value of f(a) and how to achieve it is as follows:

• f(\{0,0\}): 0 (Nothing can be done)
• f(\{0,1\}): 1 (Nothing can be done)
• f(\{0,2\}): 0 (Select Square 2, then Square 1)
• f(\{1,0\}): 0 (Select Square 1)
• f(\{1,1\}): 1 (Select Square 1)
• f(\{1,2\}): 0 (Select Square 1, Square 2, then Square 1)
• f(\{2,0\}): 2 (Nothing can be done)
• f(\{2,1\}): 3 (Nothing can be done)
• f(\{2,2\}): 3 (Select Square 2)

Sample Input 2

20 17

Sample Output 2

983853488

Problem Statement

In some place in the Arctic Ocean, there are H rows and W columns of ice pieces floating on the sea. We regard this area as a grid, and denote the square at the i-th row and j-th column as Square (i,j). The ice piece floating in each square is either thin ice or an iceberg, and a penguin lives in one of the squares that contain thin ice. There are no ice pieces floating outside the grid.

The ice piece at Square (i,j) is represented by the character S_{i,j}. S_{i,j} is +, # or P, each of which means the following:

• +: Occupied by thin ice.
• #: Occupied by an iceberg.
• P: Occupied by thin ice. The penguin lives here.

When summer comes, unstable thin ice that is not held between some pieces of ice collapses one after another. Formally, thin ice at Square (i,j) will collapse when it does NOT satisfy either of the following conditions:

• Both Square (i-1,j) and Square (i+1,j) are occupied by an iceberg or uncollapsed thin ice.
• Both Square (i,j-1) and Square (i,j+1) are occupied by an iceberg or uncollapsed thin ice.

When a collapse happens, it may cause another. Note that icebergs do not collapse.

Now, a mischievous tourist comes here. He will do a little work so that, when summer comes, the thin ice inhabited by the penguin will collapse. He can smash an iceberg with a hammer to turn it to thin ice. At least how many icebergs does he need to smash?

Constraints

• 1 \leq H,W \leq 40
• S_{i,j} is +, # or P.
• S contains exactly one P.

Sample Input 1

3 3
+#+
#P#
+#+

Sample Output 1

2

For example, when the right and bottom icebergs are changed to thin ice, collapses happen as follows:

+#+    .#.    .#.    .#.
#P+ -> #P+ -> #P. -> #..
+++    .+.    ...    ...

Sample Input 2

6 6
#+++++
+++#++
#+++++
+++P+#
+##+++
++++#+

Sample Output 2

1

Sample Input 3

40 40
#++#+++++#+#+#+##+++++++##+#+++#++##++##
+##++++++++++#+###+##++++#+++++++++#++##
+++#+++++#++#++####+++#+#+###+++##+++#++
+++#+######++##+#+##+#+++#+++++++++#++#+
+++##+#+#++#+++#++++##+++++++++#++#+#+#+
#++#+++#+#++++##+#+#+++##+#+##+#++++##++
++#+##+++#++####+#++##++#+++#+#+#++++#++
+#+###++++++##++++++#++##+#####++#++##++
##+##+#+++#+#+##++#+###+######++++#+###+
+++#+++##+#####+#+#++++#+#+++++#+##++##+
#+++#+##+++++++#++#++++++++++###+#++#+#+
##+++##++#+++++#++++#++#+##++#+#+#++##+#
##+++#+###+++++##++#+#+++####+#+++++#+++
+++#++#++#+++++++++#++###++++++++###+##+
++#+++#++++++#####++##++#+++#+++++#++++#
++#++#+##++++#####+###+++####+#+#+######
++++++##+++++##+++++#++###++#++##+++++++
+#++++##++++++#++++#+#++++#++++##+++##+#
+++++++#+#++##+##+#+++++++###+###++##+++
++++++#++###+#+#+++##+#++++++#++#+#++#+#
##+##++++++#+++++#++#+#++##+++#+#+++##+#
#+++#+#+##+#+##++#P#++#++++++##++#+#++##
#+++#++##+##+#++++#++#++##++++++#+#+#+++
++++####+#++#####+++#+###+#++###++++#++#
#+#++####++##++#+#+#+##+#+#+##++++##++#+
+###+###+#+##+++#++++++#+#++++###+#+++++
+++#+++++#+++#+++++##++++++++###++#+#+++
+#+#++#+#++++++###+#++##+#+##+##+#+#####
#++++++++#+#+###+######++#++#+++++++++++
##+++##+#+#++#++#++#++++++#++##+#+#++###
+#+#+#+++++++#+++++++######+##++#++##+##
++#+++#+###+#++###+++#+++#+#++++#+###+++
#+#+###++#+#####+++++#+####++#++#+###+++
+#+##+#++#++##+++++++######++#++++++++++
+####+#+#+++++##+#+#++#+#++#+++##++++#+#
#++##++#+#+++++##+#++++####+++++###+#+#+
##+#++#++#+##+#+#++##++###+###+#+++++##+
##++###+###+#+#++#++#########+++###+#+##
+++#+++#++++++++++#+#+++#++#++###+####+#
++##+###+++++++##+++++#++#++++++++++++++

Sample Output 3

151

Sample Input 4

1 1
P

Sample Output 4

0

Problem Statement

2^N players competed in a tournament. Each player has a unique ID number from 1 through 2^N. When two players play a match, the player with the smaller ID always wins.

This tournament was a little special, in which losers are not eliminated to fully rank all the players.

We will call such a tournament that involves 2^n players a full tournament of level n. In a full tournament of level n, the players are ranked as follows:

• In a full tournament of level 0, the only player is ranked first.
• In a full tournament of level n\ (1 \leq n), initially all 2^n players are lined up in a row. Then:
• First, starting from the two leftmost players, the players are successively divided into 2^{n-1} pairs of two players.
• Each of the pairs plays a match. The winner enters the "Won" group, and the loser enters the "Lost" group.
• The players in the "Won" group are lined up in a row, maintaining the relative order in the previous row. Then, a full tournament of level n-1 is held to fully rank these players.
• The players in the "Lost" group are also ranked in the same manner, then the rank of each of these players increases by 2^{n-1}.

For example, the figure below shows how a full tournament of level 3 progresses when eight players are lined up in the order 3,4,8,6,2,1,7,5. The list of the players sorted by the final ranking will be 1,3,5,6,2,4,7,8.

Takahashi has a sheet of paper with the list of the players sorted by the final ranking in the tournament, but some of it blurred and became unreadable. You are given the information on the sheet as a sequence A of length N. When A_i is 1 or greater, it means that the i-th ranked player had the ID A_i. If A_i is 0, it means that the ID of the i-th ranked player is lost.

Determine whether there exists a valid order in the first phase of the tournament which is consistent with the sheet. If it exists, provide one such order.

Constraints

• 1 \leq N \leq 18
• 0 \leq A_i \leq 2^N
• No integer, except 0, occurs more than once in A_i.

Sample Input 1

3
0 3 0 6 0 0 0 8

Sample Output 1

YES
3 4 8 6 2 1 7 5

This is the same order as the one in the statement.

Sample Input 2

1
2 1

Sample Output 2

NO

Problem Statement

Ringo has a tree with N vertices. The i-th of the N-1 edges in this tree connects Vertex A_i and Vertex B_i and has a weight of C_i. Additionally, Vertex i has a weight of X_i.

Here, we define f(u,v) as the distance between Vertex u and Vertex v, plus X_u + X_v.

We will consider a complete graph G with N vertices. The cost of its edge that connects Vertex u and Vertex v is f(u,v). Find the minimum spanning tree of G.

Constraints

• 2 \leq N \leq 200,000
• 1 \leq X_i \leq 10^9
• 1 \leq A_i,B_i \leq N
• 1 \leq C_i \leq 10^9
• The given graph is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

22

We connect the following pairs: Vertex 1 and 2, Vertex 1 and 4, Vertex 3 and 4. The costs are 5, 8 and 9, respectively, for a total of 22.

Sample Input 2

6
44 23 31 29 32 15
1 2 10
1 3 12
1 4 16
4 5 8
4 6 15

Sample Output 2

359

Sample Input 3

2
1000000000 1000000000
2 1 1000000000

Sample Output 3

3000000000