Problem Statement

For positive integers x and y, define f(x, y) as the remainder of (x + y) divided by 10^8.

You are given a sequence of positive integers A = (A_1, \ldots, A_N) of length N. Find the value of the following expression:

Constraints

• 2 \leq N \leq 3\times 10^5
• 1 \leq A_i < 10^8
• All input values are integers.

Sample Input 1

3
3 50000001 50000002

Sample Output 1

100000012

• f(A_1,A_2)=50000004
• f(A_1,A_3)=50000005
• f(A_2,A_3)=3

Thus, the answer is f(A_1,A_2) + f(A_1,A_3) + f(A_2,A_3) = 100000012.

Note that you are not asked to compute the remainder of the sum divided by 10^8.

Sample Input 2

5
1 3 99999999 99999994 1000000

Sample Output 2

303999988

Problem Statement

Takahashi is a martial artist. There are N moves that a martial artist can learn, called Move 1, 2, \ldots, N. For each 1 \leq i \leq N, it takes T_i minutes of practice to learn Move i. Additionally, at the beginning of that practice, all of the Moves A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} must be already learned. Here, it is guaranteed that A_{i,j} < i for each 1 \leq j \leq K_i.

Takahashi has not learned any move at time 0. He cannot practice for more than one move simultaneously, nor can he stop a practice he has already started. Find the minimum number of minutes needed for Takahashi to learn Move N.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq T_i \leq 10^9
• 0 \leq K_i < i
• 1 \leq A_{i,j} < i
• \sum_{i=1}^N K_i \leq 2\times 10^5
• A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} are all distinct.
• All values in input are integers.

Sample Input 1

3
3 0
5 1 1
7 1 1

Sample Output 1

10

Here is one possible plan for Takahashi.

• At time 0, start practicing for Move 1 to learn Move 1 at time 3.
• Then, at time 3, start practicing for Move 3 to learn Move 3 at time 10.

Here, Takahashi spends 3+7=10 minutes to learn Move 3, which is the fastest possible. Note that he does not need to learn Move 2 to learn Move 3.

Sample Input 2

5
1000000000 0
1000000000 0
1000000000 0
1000000000 0
1000000000 4 1 2 3 4

Sample Output 2

5000000000

Note that the answer may not fit into a 32-bit integer.

Problem Statement

Initially, there are N sizes of slimes.
Specifically, for each 1\leq i\leq N, there are C_i slimes of size S_i.

Takahashi can repeat slime synthesis any number of times (possibly zero) in any order.
Slime synthesis is performed as follows.

• Choose two slimes of the same size. Let this size be X, and a new slime of size 2X appears. Then, the two original slimes disappear.

Takahashi wants to minimize the number of slimes. What is the minimum number of slimes he can end up with by an optimal sequence of syntheses?

Constraints

• 1\leq N\leq 10^5
• 1\leq S_i\leq 10^9
• 1\leq C_i\leq 10^9
• S_1,S_2,\ldots,S_N are all different.
• All input values are integers.

Sample Input 1

3
3 3
5 1
6 1

Sample Output 1

3

Initially, there are three slimes of size 3, one of size 5, and one of size 6.
Takahashi can perform the synthesis twice as follows:

• First, perform the synthesis by choosing two slimes of size 3. There will be one slime of size 3, one of size 5, and two of size 6.
• Next, perform the synthesis by choosing two slimes of size 6. There will be one slime of size 3, one of size 5, and one of size 12.

No matter how he repeats the synthesis from the initial state, he cannot reduce the number of slimes to 2 or less, so you should print 3.

Sample Input 2

3
1 1
2 1
3 1

Sample Output 2

3

He cannot perform the synthesis.

Sample Input 3

1
1000000000 1000000000

Sample Output 3

13

Problem Statement

You are given N strings consisting of lowercase English letters. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

For two strings x and y, \mathrm{LCP}(x, y) is defined to be the maximum integer n that satisfies all of the following conditions:

• The lengths of x and y are both at least n.
• For all integers i between 1 and n, inclusive, the i-th character of x and that of y are equal.

Find the following value for all i = 1, 2, \dots, N:

• \displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j)

Constraints

• 2 \leq N \leq 5 \times 10^5
• N is an integer.
• S_i is a string of length at least 1 consisting of lowercase English letters (i = 1, 2, \dots, N).
• The sum of lengths of S_i is at most 5 \times 10^5.

Sample Input 1

3
abc
abb
aac

Sample Output 1

2
2
1

\mathrm{LCP}(S_1, S_2) = 2, \mathrm{LCP}(S_1, S_3) = 1, and \mathrm{LCP}(S_2, S_3) = 1.

Sample Input 2

11
abracadabra
bracadabra
racadabra
acadabra
cadabra
adabra
dabra
abra
bra
ra
a

Sample Output 2

4
3
2
1
0
1
0
4
3
2
1

Problem Statement

Takahashi and Aoki will play a game using cards with numbers written on them.

Initially, Takahashi has N cards with numbers A_1, \ldots, A_N in his hand, Aoki has M cards with numbers B_1, \ldots, B_M in his hand, and there are L cards with numbers C_1, \ldots, C_L on the table.
Throughout the game, both Takahashi and Aoki know all the numbers on all the cards, including the opponent's hand.

Starting with Takahashi, they take turns performing the following action:

• Choose one card from his hand and put it on the table. Then, if there is a card on the table with a number less than the number on the card he just played, he may take one such card from the table into his hand.

The player who cannot make a move first loses, and the other player wins. Determine who wins if both players play optimally.

It can be proved that the game always ends in a finite number of moves.

Constraints

• 1 \leq N, M, L
• N + M + L \leq 12
• 1 \leq A_i, B_i, C_i \leq 10^9
• All input values are integers.

Sample Input 1

1 1 2
2
4
1 3

Sample Output 1

Aoki

The game may proceed as follows (not necessarily optimal moves):

• Takahashi plays 2 from his hand to the table, and takes 1 from the table into his hand. Now, Takahashi's hand is (1), Aoki's hand is (4), and the table cards are (2,3).
• Aoki plays 4 from his hand to the table, and takes 2 into his hand. Now, Takahashi's hand is (1), Aoki's hand is (2), and the table cards are (3,4).
• Takahashi plays 1 from his hand to the table. Now, Takahashi's hand is (), Aoki's hand is (2), and the table cards are (1,3,4).
• Aoki plays 2 from his hand to the table. Now, Takahashi's hand is (), Aoki's hand is (), and the table cards are (1,2,3,4).
• Takahashi cannot make a move and loses; Aoki wins.

Sample Input 2

4 4 4
98 98765 987654 987654321
987 9876 9876543 98765432
123 12345 1234567 123456789

Sample Output 2

Takahashi

Sample Input 3

1 1 8
10
10
1 2 3 4 5 6 7 8

Sample Output 3

Aoki