Problem Statement

Takahashi is growing a plant. Its height at the time of germination is 0\,\mathrm{cm}. Considering the day of germination as day 0, its height increases by 2^i\,\mathrm{cm} day i's night (0 \le i).

Takahashi's height is H\,\mathrm{cm}.

Every morning, Takahashi measures his height against this plant. Find the first day such that the plant's height is strictly greater than Takahashi's height in the morning.

Constraints

• 1 \leq H \leq 10^{9}
• All input values are integers.

Sample Input 1

54

Sample Output 1

6

The plant's height in the mornings of days 1, 2, 3, 4, 5, 6 will be 1\,\mathrm{cm}, 3\,\mathrm{cm}, 7\,\mathrm{cm}, 15\,\mathrm{cm}, 31\,\mathrm{cm}, 63\,\mathrm{cm}, respectively. The plant becomes taller than Takahashi in the morning day 6, so print 6.

Sample Input 2

7

Sample Output 2

4

The plant's height will be 7\,\mathrm{cm} in the morning of day 3 and 15\,\mathrm{cm} in the morning day 4. The plant becomes taller than Takahashi in the morning of day 4, so print 4. Note that, in the morning of day 3, the plant is as tall as Takahashi, but not taller.

Sample Input 3

262144

Sample Output 3

19

Problem Statement

N AtCoder users have gathered to play AtCoder RPS 2. The i-th user's name is S_i and their rating is C_i.

AtCoder RPS 2 is played as follows:

• Assign the numbers 0, 1, \dots, N - 1 to the users in lexicographical order of their usernames.
• Let T be the sum of the ratings of the N users. The user assigned the number T \bmod N is the winner.

Print the winner's username.

Constraints

• 1 \leq N \leq 100
• S_i is a string consisting of lowercase English letters with length between 3 and 16, inclusive.
• S_1, S_2, \dots, S_N are all distinct.
• 1 \leq C_i \leq 4229
• C_i is an integer.

Sample Input 1

3
takahashi 2
aoki 6
snuke 5

Sample Output 1

snuke

The sum of the ratings of the three users is 13. Sorting their names in lexicographical order yields aoki, snuke, takahashi, so aoki is assigned number 0, snuke is 1, and takahashi is 2.

Since 13 \bmod 3 = 1, print snuke, who is assigned number 1.

Sample Input 2

3
takahashi 2813
takahashixx 1086
takahashix 4229

Sample Output 2

takahashix

Problem Statement

Takahashi has N cards from the card game "AtCoder Magics." The i-th card will be called card i. Each card has two parameters: strength and cost. Card i has a strength of A_i and a cost of C_i.

He does not like weak cards, so he will discard them. Specifically, he will repeat the following operation until it can no longer be performed:

• Choose two cards x and y such that A_x > A_y and C_x < C_y. Discard card y.

It can be proved that the set of remaining cards when the operations can no longer be performed is uniquely determined. Find this set of cards.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i, C_i \leq 10^9
• A_1, A_2, \dots ,A_N are all distinct.
• C_1, C_2, \dots ,C_N are all distinct.
• All input values are integers.

Sample Input 1

3
2 4
1 1
3 2

Sample Output 1

2
2 3

Focusing on cards 1 and 3, we have A_1 < A_3 and C_1 > C_3, so card 1 can be discarded.

No further operations can be performed. At this point, cards 2 and 3 remain, so print them.

Sample Input 2

5
1 1
10 2
100 3
1000 4
10000 5

Sample Output 2

5
1 2 3 4 5

In this case, no cards can be discarded.

Sample Input 3

6
32 101
65 78
2 29
46 55
103 130
52 40

Sample Output 3

4
2 3 5 6

Problem Statement

The pattern of AtCoder's wallpaper can be represented on the xy-plane as follows:

• The plane is divided by the following three types of lines:
  • x = n (where n is an integer)
  • y = n (where n is an even number)
  • x + y = n (where n is an even number)
• Each region is painted black or white. Any two regions adjacent along one of these lines are painted in different colors.
• The region containing (0.5, 0.5) is painted black.

The following figure shows a part of the pattern.

You are given integers A, B, C, D. Consider a rectangle whose sides are parallel to the x- and y-axes, with its bottom-left vertex at (A, B) and its top-right vertex at (C, D). Calculate the area of the regions painted black inside this rectangle, and print twice that area.

It can be proved that the output value will be an integer.

Constraints

• -10^9 \leq A, B, C, D \leq 10^9
• A < C and B < D.
• All input values are integers.

Sample Input 1

0 0 3 3

Sample Output 1

10

We are to find the area of the black-painted region inside the following square:

The area is 5, so print twice that value: 10.

Sample Input 2

-1 -2 1 3

Sample Output 2

11

The area is 5.5, which is not an integer, but the output value is an integer.

Sample Input 3

-1000000000 -1000000000 1000000000 1000000000

Sample Output 3

4000000000000000000

This is the case with the largest rectangle, where the output still fits into a 64-bit signed integer.

Problem Statement

Takahashi and Aoki are playing a game using N cards. The front side of the i-th card has A_i written on it, and the back side has B_i written on it. Initially, the N cards are laid out on the table. With Takahashi going first, the two players take turns performing the following operation:

• Choose a pair of cards from the table such that either the numbers on their front sides are the same or the numbers on their back sides are the same, and remove these two cards from the table. If no such pair of cards exists, the player cannot perform the operation.

The player who is first to be unable to perform the operation loses, and the other player wins. Determine who wins if both players play optimally.

Constraints

• 1 \leq N \leq 18
• 1 \leq A_i, B_i \leq 10^9
• All input values are integers.

Sample Input 1

5
1 9
2 5
4 9
1 4
2 5

Sample Output 1

Aoki

If Takahashi first removes

• the first and third cards: Aoki can win by removing the second and fifth cards.

• the first and fourth cards: Aoki can win by removing the second and fifth cards.

• the second and fifth cards: Aoki can win by removing the first and third cards.

These are the only three pairs of cards Takahashi can remove in his first move, and Aoki can win in all cases. Therefore, the answer is Aoki.

Sample Input 2

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

Sample Output 2

Takahashi

Problem Statement

You are given an integer sequence A of length N.

For each t = 1, 2, \dots, N, determine whether A_t is included in a longest increasing subsequence of A.

Here, A_t is included in a longest increasing subsequence of A if and only if the following holds:

• Let L be the length of a longest increasing subsequence of A. There exists a strictly increasing integer sequence i = (i_1, i_2, \dots, i_L) \ (i_1 < i_2 < \dots < i_L), where each element is between 1 and N, inclusive, that satisfies all of the following conditions:

  • A_{i_1} < A_{i_2} < \dots < A_{i_L}.
  • i_k = t for some k \ (1 \leq k \leq L).

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• The sum of N across all test cases is at most 2 \times 10^5.

Sample Input 1

1
5
2 1 4 5 3

Sample Output 1

4
1 2 3 4

One of the longest increasing subsequences is (2, 4, 5), with a length of 3. Another longest increasing subsequence is (1, 4, 5). However, no longest increasing subsequence includes A_5.

Therefore, print 1, 2, 3, 4.

Sample Input 2

2
6
2 5 3 4 3 4
5
10000 1000 100 1 10

Sample Output 2

5
1 3 4 5 6
2
4 5

Problem Statement

You are given N strings S_1, S_2, \ldots, S_N consisting of lowercase English letters and N positive integers A_1, A_2, \ldots, A_N.

A subset T of \lbrace 1, 2, \ldots, N \rbrace is called a good set if there is no pair i, j \in T (i \neq j) such that S_i is a substring of S_j.

Find the maximum possible value of \displaystyle \sum_{i \in T} A_i for a good set T.

Constraints

• 1 \leq N \leq 100
• S_i is a string consisting of lowercase English letters.
• 1 \leq |S_i|
• |S_1| + |S_2| + \ldots + |S_N| \leq 5000
• 1 \leq A_i \leq 10^9

Sample Input 1

4
atcoder
at
coder
code
5 2 3 4

Sample Output 1

6

The possible good sets T and their corresponding \displaystyle \sum_{i \in T} A_i are as follows:

• T = \lbrace 1 \rbrace: \displaystyle \sum_{i \in T} A_i = 5
• T = \lbrace 2 \rbrace: \displaystyle \sum_{i \in T} A_i = 2
• T = \lbrace 3 \rbrace: \displaystyle \sum_{i \in T} A_i = 3
• T = \lbrace 4 \rbrace: \displaystyle \sum_{i \in T} A_i = 4
• T = \lbrace 2, 3 \rbrace: \displaystyle \sum_{i \in T} A_i = 5
• T = \lbrace 2, 4 \rbrace: \displaystyle \sum_{i \in T} A_i = 6

The maximum among them is 6, so print 6.

Sample Input 2

10
abcd
abc
ab
a
b
c
d
ab
bc
cd
100 10 50 30 60 90 80 70 40 20

Sample Output 2

260