Problem Statement

In the calendar of AtCoder Kingdom, a year consists of M months from month 1 to month M, and each month consists of D days from day 1 to day D.

What day follows year y, month m, day d in this calendar?

Constraints

• 1000 \leq y \leq 9000
• 1 \leq m \leq M \leq 99
• 1 \leq d \leq D \leq 99
• All input values are integers.

Sample Input 1

12 30
2023 12 30

Sample Output 1

2024 1 1

In the calendar of the kingdom, a year consists of 12 months, and each month consists of 30 days. Thus, the day following year 2023, month 12, day 30 is year 2024, month 1, day 1.

Sample Input 2

36 72
6789 23 45

Sample Output 2

6789 23 46

In the calendar of the kingdom, one year consists of 36 months, and each month consists of 72 days. Thus, the day following year 6789, month 23, day 45 is year 6789, month 23, day 46.

Sample Input 3

12 30
2012 6 20

Sample Output 3

2012 6 21

Problem Statement

In the Kingdom of AtCoder, residents are required to shout their love for takoyaki at A o'clock every day.

Takahashi, who lives in the Kingdom of AtCoder, goes to bed at B o'clock and wakes up at C o'clock every day (in the 24-hour clock). He can shout his love for takoyaki when he is awake, but cannot when he is asleep. Determine whether he can shout his love for takoyaki every day. Here, a day has 24 hours, and his sleeping time is less than 24 hours.

Constraints

• 0\leq A,B,C\lt 24
• A, B, and C are pairwise different.
• All input values are integers.

Sample Input 1

21 8 14

Sample Output 1

Yes

Takahashi goes to bed at 8 o'clock and wakes up at 14 o'clock every day. He is awake at 21 o'clock, so he can shout his love for takoyaki every day. Therefore, print Yes.

Sample Input 2

0 21 7

Sample Output 2

No

Takahashi goes to bed at 21 o'clock and wakes up at 7 o'clock every day. He is not awake at 0 o'clock, so he cannot shout his love for takoyaki every day. Therefore, print No.

Sample Input 3

10 7 17

Sample Output 3

No

Problem Statement

You are given N strings S_1, S_2, \ldots, S_N consisting of lowercase English letters.

Define N digits C_1, C_2, \ldots, C_N as follows:

• If the first character of S_i is one of a, b, c, then C_i= 2
• If the first character of S_i is one of d, e, f, then C_i= 3
• If the first character of S_i is one of g, h, i, then C_i= 4
• If the first character of S_i is one of j, k, l, then C_i= 5
• If the first character of S_i is one of m, n, o, then C_i= 6
• If the first character of S_i is one of p, q, r, s, then C_i= 7
• If the first character of S_i is one of t, u, v, then C_i= 8
• If the first character of S_i is one of w, x, y, z, then C_i= 9

Output the string obtained by concatenating C_1, C_2, \ldots, C_N in this order.

Constraints

• 1 \leq N \leq 10
• N is an integer.
• S_i is a string of length between 1 and 10, inclusive, consisting of lowercase English letters.

Sample Input 1

2
algorithm heuristic

Sample Output 1

24

• The first character of S_1= algorithm is a, so C_1= 2.
• The first character of S_2= heuristic is h, so C_2= 4.

Thus, output 24, which is their concatenation.

Sample Input 2

3
i love you

Sample Output 2

459

Problem Statement

You are given an integer N and a sequence S=(S_1,\ldots,S_N) of length N.

Find a sequence A=(A_1,\ldots,A_N) of length N that satisfies the following condition for all k=1,\ldots,N:

• A_1+A_2+\ldots+A_k = S_k.

Such a sequence A always exists and is unique.

Constraints

• 1 \leq N \leq 10
• -10^9\leq S_i \leq 10^9
• All values in the input are integers.

Sample Input 1

3
3 4 8

Sample Output 1

3 1 4

The sequence in the output actually satisfies all the conditions:

• A_1=3=S_1;
• A_1+A_2=3+1=4=S_2;
• A_1+A_2+A_3=3+1+4=8=S_3.

Sample Input 2

10
314159265 358979323 846264338 -327950288 419716939 -937510582 97494459 230781640 628620899 -862803482

Sample Output 2

314159265 44820058 487285015 -1174214626 747667227 -1357227521 1035005041 133287181 397839259 -1491424381

Problem Statement

There are N people numbered from 1 to N visiting a conveyor belt sushi restaurant. The gourmet level of person i is A_i.

Now, M pieces of sushi will be placed on the conveyor belt. The deliciousness of the j-th sushi is B_j. Each piece of sushi passes in front of people 1, 2, \dots, N in this order. Each person, when a sushi whose deliciousness is not less than their gourmet level passes in front of them, will take and eat that sushi; otherwise, they do nothing. A sushi that person i takes and eats will no longer pass in front of person j\ (j > i).

For each of the M pieces of sushi, determine who eats that sushi, or if nobody eats it.

Constraints

• 1 \leq N, M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq 2 \times 10^5
• All input values are integers.

Sample Input 1

3 3
3 8 2
5 2 1

Sample Output 1

1
3
-1

• For the 1st sushi:
  • It first passes in front of person 1. Since B_1 \geq A_1, person 1 takes and eats it.
  • It will not pass in front of person 2 and 3.
• For the 2nd sushi:
  • It first passes in front of person 1. Since B_2 < A_1, person 1 does nothing.
  • Next, it passes in front of person 2. Since B_2 < A_2, person 2 does nothing.
  • Finally, it passes in front of person 3. Since B_2 \geq A_3, person 3 takes and eats it.
• For the 3rd sushi:
  • It first passes in front of person 1. Since B_3 < A_1, person 1 does nothing.
  • Next, it passes in front of person 2. Since B_3 < A_2, person 2 does nothing.
  • Finally, it passes in front of person 3. Since B_3 < A_3, person 3 does nothing.
  • Therefore, nobody eats this sushi.

Sample Input 2

3 3
1 1 1
1 1 1

Sample Output 2

1
1
1

Sample Input 3

10 5
60 83 76 45 70 91 37 58 94 22
70 39 52 33 18

Sample Output 3

1
7
4
10
-1

Problem Statement

You are given an undirected graph with N vertices and M edges, where the vertices are numbered 1 through N and the edges are numbered 1 through M. Edge i connects vertices u_i and v_i.
To make the graph simple by removing edges, what is the minimum number of edges that must be removed?
Here, a graph is called simple if and only if it does not contain self-loops or multi-edges.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 5 \times 10^5
• 1 \leq u_i \leq N
• 1 \leq v_i \leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

2

By removing edges 3 and 5, the graph becomes simple. This is one of the ways to remove the minimum number of edges, so the answer is 2.

Sample Input 2

1 0

Sample Output 2

0

Sample Input 3

6 10
6 2
4 1
5 1
6 6
5 3
5 1
1 4
6 4
4 2
5 6

Sample Output 3

3

Problem Statement

There are N bags, labeled bag 1, bag 2, \ldots, bag N.
Bag i (1 \leq i \leq N) contains A_i stones.

Takahashi can perform the following operation any number of times, possibly zero:

Choose two bags A and B, and move all stones from bag A into bag B.

Find the number of different possible values for the following after repeating the operation.

• B_1 \oplus B_2 \oplus \cdots \oplus B_N, where B_i is the final number of stones in bag i.
  Here, \oplus denotes bitwise XOR.

It can be proved that under the constraints of this problem, the number of possible values is finite.

Constraints

• 2 \leq N \leq 12
• 1 \leq A_i \leq 10^{17}
• All input values are integers.

Sample Input 1

3
2 5 7

Sample Output 1

3

For example, if Takahashi chooses bags 1 and 3 for the operation, then the numbers of stones in bags 1, 2, 3 become 0, 5, 9.
If he stops at this point, the XOR is 0 \oplus 5 \oplus 9 = 12.

The other possible XOR values after repeating the operation are 0 and 14.
Therefore, the possible values are 0, 12, 14; there are three values, so the output is 3.

Sample Input 2

2
100000000000000000 100000000000000000

Sample Output 2

2

Sample Input 3

6
71 74 45 34 31 60

Sample Output 3

84

Problem Statement

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

Each square contains an integer. For each i = 1, 2, \ldots, N, the square (r_i, c_i) contains a positive integer a_i. The other square contains a 0.

Initially, there is a piece on the square (R, C). Takahashi can move the piece to a square other than the square it occupies now, any number of times. However, when moving the piece, both of the following conditions must be satisfied.

• The integer written on the square to which the piece is moved is strictly greater than the integer written on the square from which the piece is moved.
• The squares to and from which the piece is moved are in the same row or the same column.

For each i = 1, 2, \ldots, N, print the maximum number of times Takahashi can move the piece when (R, C) = (r_i, c_i).

Constraints

• 2 \leq H, W \leq 2 \times 10^5
• 1 \leq N \leq \min(2 \times 10^5, HW)
• 1 \leq r_i \leq H
• 1 \leq c_i \leq W
• 1 \leq a_i \leq 10^9
• i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1
0
2
0
3
1
0

The grid contains the following integers.

4 7 0
3 0 5
2 5 5

• When (R, C) = (r_1, c_1) = (1, 1), you can move the piece once by moving it as (1, 1) \rightarrow (1, 2).
• When (R, C) = (r_2, c_2) = (1, 2), you cannot move the piece at all.
• When (R, C) = (r_3, c_3) = (2, 1), you can move the piece twice by moving it as (2, 1) \rightarrow (1, 1) \rightarrow (1, 2).
• When (R, C) = (r_4, c_4) = (2, 3), you cannot move the piece at all.
• When (R, C) = (r_5, c_5) = (3, 1), you can move the piece three times by moving it as (3, 1) \rightarrow (2, 1) \rightarrow (1, 1) \rightarrow (1, 2).
• When (R, C) = (r_6, c_6) = (3, 2), you can move the piece once by moving it as (3, 2) \rightarrow (1, 2).
• When (R, C) = (r_7, c_7) = (3, 3), you cannot move the piece at all.

Sample Input 2

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

Sample Output 2

2
4
1
5
3
6
6
2
7
0
0
4
1
5
3
0
5
2
4
0

Problem Statement

Takahashi has an integer x. Initially, x = 0.

There are N operations. The i-th operation (1 \leq i \leq N) is represented by two integers t_i and y_i as follows:

• If t_i = 1, replace x with y_i.
• If t_i = 2, replace x with x + y_i.

Takahashi may skip any number between 0 and K (inclusive) of the operations. When he performs the remaining operations once each without changing the order, find the maximum possible final value of x.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq N
• t_i \in \{1,2\} \, (1 \leq i \leq N)
• |y_i| \leq 10^9 \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

3

If he skips the 5-th operation, x changes as 0 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3, so x results in 3. This is the maximum.

Sample Input 2

1 0
2 -1000000000

Sample Output 2

-1000000000

Sample Input 3

10 3
2 3
2 -1
1 4
2 -1
2 5
2 -9
2 2
1 -6
2 5
2 -3

Sample Output 3

15