Problem Statement

N players with ID numbers 1, 2, \ldots, N are playing a card game.
Each player plays one card.

Each card has two parameters: color and rank, both of which are represented by positive integers.
For i = 1, 2, \ldots, N, the card played by player i has a color C_i and a rank R_i. All of R_1, R_2, \ldots, R_N are different.

Among the N players, one winner is decided as follows.

• If one or more cards with the color T are played, the player who has played the card with the greatest rank among those cards is the winner.
• If no card with the color T is played, the player who has played the card with the greatest rank among the cards with the color of the card played by player 1 is the winner. (Note that player 1 may win.)

Print the ID number of the winner.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq T \leq 10^9
• 1 \leq C_i \leq 10^9
• 1 \leq R_i \leq 10^9
• i \neq j \implies R_i \neq R_j
• All values in the input are integers.

Sample Input 1

4 2
1 2 1 2
6 3 4 5

Sample Output 1

4

Cards with the color 2 are played. Thus, the winner is player 4, who has played the card with the greatest rank, 5, among those cards.

Sample Input 2

4 2
1 3 1 4
6 3 4 5

Sample Output 2

1

No card with the color 2 is played. Thus, the winner is player 1, who has played the card with the greatest rank, 6, among the cards with the color of the card played by player 1 (color 1).

Sample Input 3

2 1000000000
1000000000 1
1 1000000000

Sample Output 3

1

Problem Statement

Takahashi bought a table clock.
The clock shows the time as shown in Figure 1 at \mathrm{AB}:\mathrm{CD} in the 24-hour system.
For example, the clock in Figure 2 shows 7:58.

The format of the time is formally described as follows.
Suppose that the current time is m minutes past h in the 24-hour system. Here, the 24-hour system represents the hour by an integer between 0 and 23 (inclusive), and the minute by an integer between 0 and 59 (inclusive).
Let A be the tens digit of h, B be the ones digit of h, C be the tens digit of m, and D be the ones digit of m. (Here, if h has only one digit, we consider that it has a leading zero; the same applies to m.)
Then, the clock shows A in its top-left, B in its bottom-left, C in its top-right, and D in its bottom-right.

Takahashi has decided to call a time a confusing time if it satisfies the following condition:

• after swapping the top-right and bottom-left digits on the clock, it still reads a valid time in the 24-hour system.

For example, the clock in Figure 3 shows 20:13. After swapping its top-right and bottom-left digits, it reads 21:03. Thus, 20:13 is a confusing time.

The clock now shows H:M.
Find the next confusing time (including now) in the 24-hour system.

Constraints

• 0 \leq H \leq 23
• 0 \leq M \leq 59
• H and M are integers.

Sample Input 1

1 23

Sample Output 1

1 23

1:23 is a confusing time because, after swapping its top-right and bottom-left digits on the clock, it reads 2:13.
Thus, the answer is 1:23.
Your answer is considered correct even if you print 01 23 with a leading zero.

Sample Input 2

19 57

Sample Output 2

20 0

The next confusing time after 19:57 is 20:00.

Sample Input 3

20 40

Sample Output 3

21 0

Note that 24:00 is an invalid notation in the 24-hour system.

Problem Statement

There are N people, each of whom is either a child or an adult. The i-th person has a weight of W_i.
Whether each person is a child or an adult is specified by a string S of length N consisting of 0 and 1.
If the i-th character of S is 0, then the i-th person is a child; if it is 1, then the i-th person is an adult.

When Takahashi the robot is given a real number X, Takahashi judges a person with a weight less than X to be a child and a person with a weight more than or equal to X to be an adult.
For a real value X, let f(X) be the number of people whom Takahashi correctly judges whether they are children or adults.

Find the maximum value of f(X) for all real values of X.

Constraints

• 1\leq N\leq 2\times 10^5
• S is a string of length N consisting of 0 and 1.
• 1\leq W_i\leq 10^9
• N and W_i are integers.

Sample Input 1

5
10101
60 45 30 40 80

Sample Output 1

4

When Takahashi is given X=50, it judges the 2-nd, 3-rd, and 4-th people to be children and the 1-st and 5-th to be adults.
In reality, the 2-nd and 4-th are children, and the 1-st, 3-rd, and 5-th are adults, so the 1-st, 2-nd, 4-th, and 5-th people are correctly judged. Thus, f(50)=4.

This is the maximum since there is no X that judges correctly for all 5 people. Thus, 4 should be printed.

Sample Input 2

3
000
1 2 3

Sample Output 2

3

For example, X=10 achieves the maximum value f(10)=3.
Note that the people may be all children or all adults.

Sample Input 3

5
10101
60 50 50 50 60

Sample Output 3

4

For example, X=55 achieves the maximum value f(55)=4.
Note that there may be multiple people with the same weight.

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

2N people numbered 1, 2, \ldots, 2N attend a ball. They will group into N pairs and have a dance.

If Person i and Person j pair up, where i is smaller than j, the affinity of that pair is A_{i, j}.
If the N pairs have the affinity of B_1, B_2, \ldots, B_N, the total fun of the ball is the bitwise XOR of them: B_1 \oplus B_2 \oplus \cdots \oplus B_N.

Print the maximum possible total fun of the ball when the 2N people can freely group into N pairs.

Constraints

• 1 \leq N \leq 8
• 0 \leq A_{i, j} < 2^{30}
• All values in input are integers.

Sample Input 1

2
4 0 1
5 3
2

Sample Output 1

6

Let \lbrace i, j\rbrace denote a pair of Person i and Person j. There are three ways for the four people to group into two pairs, as follows.

• Group into \lbrace 1, 2\rbrace, \lbrace 3, 4\rbrace. The total fun of the ball here is A_{1, 2} \oplus A_{3, 4} = 4 \oplus 2 = 6.
• Group into \lbrace 1, 3\rbrace, \lbrace 2, 4\rbrace. The total fun of the ball here is A_{1, 3} \oplus A_{2, 4} = 0 \oplus 3 = 3.
• Group into \lbrace 1, 4\rbrace, \lbrace 2, 3\rbrace. The total fun of the ball here is A_{1, 4} \oplus A_{2, 3} = 1 \oplus 5 = 4.

Therefore, the maximum possible total fun of the ball is 6.

Sample Input 2

1
5

Sample Output 2

5

There will be just a pair of Person 1 and Person 2, where the total fun of the ball is 5.

Sample Input 3

5
900606388 317329110 665451442 1045743214 260775845 726039763 57365372 741277060 944347467
369646735 642395945 599952146 86221147 523579390 591944369 911198494 695097136
138172503 571268336 111747377 595746631 934427285 840101927 757856472
655483844 580613112 445614713 607825444 252585196 725229185
827291247 105489451 58628521 1032791417 152042357
919691140 703307785 100772330 370415195
666350287 691977663 987658020
1039679956 218233643
70938785

Sample Output 3

1073289207