Problem Statement

There was an exam consisting of three problems worth 1, 2, and 4 points.

Takahashi, Aoki, and Snuke took this exam. Takahashi scored A points, and Aoki scored B points.

Snuke solved all of the problems solved by at least one of Takahashi and Aoki, and failed to solve any of the problems solved by neither of them.

Find Snuke's score.

It can be proved that Snuke's score is uniquely determined under the Constraints of this problem.

Constraints

• 0\leq A,B \leq 7
• A and B are integers.

Sample Input 1

1 2

Sample Output 1

3

Since Takahashi scored 1 point, we see that he solved only the 1-point problem and failed to solve the other two.
Similarly, since Aoki scored 2 points, we see that he solved only the 2-point problem and failed to solve the other two.

Therefore, Snuke must have solved the 1- and 2-point problems, but not the 4-point one, which Takahashi and Aoki both failed to solve, for a score of 3 points. Thus, 3 should be printed.

Sample Input 2

5 3

Sample Output 2

7

Since Takahashi scored 5 points, we see that he solved the 1- and 4-point problems but not the 2-point one.
Similarly, since Aoki scored 3 points, we see that he solved the 1- and 2-point problems but not the 4-point one.

Therefore, each of the three problems is solved by at least one of Takahashi and Aoki, so we see that Snuke solved all of the problems, for a score of 7 points. Thus, 7 should be printed.

Sample Input 3

0 0

Sample Output 3

0

Both Takahashi and Aoki solved none of the problems. Therefore, so did Snuke. Thus, 0 should be printed.

Problem Statement

AtCoder Beginner Contest usually starts at 21:00 JST and lasts for 100 minutes.

You are given an integer K between 0 and 100 (inclusive). Print the time K minutes after 21:00 in the HH:MM format, where HH denotes the hour on the 24-hour clock and MM denotes the minute. If the hour or the minute has just one digit, append a 0 to the beginning to represent it as a 2-digit integer.

Constraints

• K is an integer between 0 and 100 (inclusive).

Sample Input 1

63

Sample Output 1

22:03

63 minutes after 21:00, it will be 22:03, so 22:03 should be printed.

The following outputs would be judged incorrect:

• 10:03
• 22:3

Sample Input 2

45

Sample Output 2

21:45

Sample Input 3

100

Sample Output 3

22:40

Problem Statement

You are given an integer N between -10^{18} and 10^{18} (inclusive).

Find an integer x between 0 and 998244353 - 1 (inclusive) that satisfies the following condition. It can be proved that such an integer is unique.

• N-x is a multiple of 998244353.

Constraints

• N is an integer between -10^{18} and 10^{18} (inclusive).

Sample Input 1

998244354

Sample Output 1

1

998244354-1 = 998244353 is a multiple of 998244353, so the condition is satisfied.

Sample Input 2

-9982443534

Sample Output 2

998244349

-9982443534-998244349= -10980687883 is a multiple of 998244353, so the condition is satisfied.

Problem Statement

There is an infinitely long piano keyboard. Is there a continuous segment within this keyboard that consists of W white keys and B black keys?

Let S be the string formed by infinitely repeating the string wbwbwwbwbwbw.

Is there a substring of S that consists of W occurrences of w and B occurrences of b?

Constraints

• W and B are integers.
• 0\leq W,B \leq 100
• W+B \geq 1

Sample Input 1

3 2

Sample Output 1

Yes

The first 15 characters of S are wbwbwwbwbwbwwbw. You can take the 11-th through 15-th characters to form the string bwwbw, which is a substring consisting of three occurrences of w and two occurrences of b.

Sample Input 2

3 0

Sample Output 2

No

The only string consisting of three occurrences of w and zero occurrences of b is www, which is not a substring of S.

Sample Input 3

92 66

Sample Output 3

Yes

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N). You can perform the following operation any number of times (possibly zero).

• Choose integers i and j with 1\leq i,j \leq N. Decrease A_i by one and increase A_j by one.

Find the minimum number of operations required to make the difference between the minimum and maximum values of A at most one.

Constraints

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

Sample Input 1

4
4 7 3 7

Sample Output 1

3

By the following three operations, the difference between the minimum and maximum values of A becomes at most one.

• Choose i=2 and j=3 to make A=(4,6,4,7).
• Choose i=4 and j=1 to make A=(5,6,4,6).
• Choose i=4 and j=3 to make A=(5,6,5,5).

You cannot make the difference between maximum and minimum values of A at most one by less than three operations, so the answer is 3.

Sample Input 2

1
313

Sample Output 2

0

Sample Input 3

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

Sample Output 3

2499999974

Problem Statement

Takahashi, who governs the Kingdom of AtCoder, has decided to change the alphabetical order of English lowercase letters.

The new alphabetical order is represented by a string X, which is a permutation of a, b, \ldots, z. The i-th character of X (1 \leq i \leq 26) would be the i-th smallest English lowercase letter in the new order.

The kingdom has N citizens, whose names are S_1, S_2, \dots, S_N, where each S_i (1 \leq i \leq N) consists of lowercase English letters.
Sort these names lexicographically according to the alphabetical order decided by Takahashi.

Constraints

• X is a permutation of a, b, \ldots, z.
• 2 \leq N \leq 50000
• N is an integer.
• 1 \leq |S_i| \leq 10 \, (1 \leq i \leq N)
• S_i consists of lowercase English letters. (1 \leq i \leq N)
• S_i \neq S_j (1 \leq i \lt j \leq N)

Sample Input 1

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

Sample Output 1

bzz
bzy
abx
caa

In the new alphabetical order set by Takahashi, b is smaller than a and z is smaller than y. Thus, sorting the citizens' names lexicographically would result in bzz, bzy, abx, caa in ascending order.

Sample Input 2

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

Sample Output 2

b
a
ac
ab
abc

Problem Statement

Takahashi has decided to give one gift to Aoki and one gift to Snuke.
There are N candidates of gifts for Aoki, and their values are A_1, A_2, \ldots,A_N.
There are M candidates of gifts for Snuke, and their values are B_1, B_2, \ldots,B_M.

Takahashi wants to choose gifts so that the difference in values of the two gifts is at most D.

Determine if he can choose such a pair of gifts. If he can, print the maximum sum of values of the chosen gifts.

Constraints

• 1\leq N,M\leq 2\times 10^5
• 1\leq A_i,B_i\leq 10^{18}
• 0\leq D \leq 10^{18}
• All values in the input are integers.

Sample Input 1

2 3 2
3 10
2 5 15

Sample Output 1

8

The difference of values of the two gifts should be at most 2.
If he gives a gift with value 3 to Aoki and another with value 5 to Snuke, the condition is satisfied, achieving the maximum possible sum of values.
Thus, 3+5=8 should be printed.

Sample Input 2

3 3 0
1 3 3
6 2 7

Sample Output 2

-1

He cannot choose gifts to satisfy the condition. Note that the candidates of gifts for a person may contain multiple gifts with the same value.

Sample Input 3

1 1 1000000000000000000
1000000000000000000
1000000000000000000

Sample Output 3

2000000000000000000

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

Sample Input 4

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

Sample Output 4

14

Problem Statement

A country has N cities and M power plants, which we collectively call places.
The places are numbered 1,2,\dots,N+M, among which Places 1,2,\dots,N are the cities and Places N+1,N+2,\dots,N+M are the power plants.

This country has E power lines. Power Line i (1 \le i \le E) connects Place U_i and Place V_i bidirectionally.
A city is said to be electrified if one can reach at least one of the power plants from the city using some power lines.

Now, Q events will happen. In the i-th (1 \le i \le Q) event, Power Line X_i breaks, making it unusable. Once a power line breaks, it remains broken in the succeeding events.

Find the number of electrified cities right after each events.

Constraints

• All values in input are integers.
• 1 \le N,M
• N+M \le 2 \times 10^5
• 1 \le Q \le E \le 5 \times 10^5
• 1 \le U_i < V_i \le N+M
• If i \neq j, then U_i \neq U_j or V_i \neq V_j.
• 1 \le X_i \le E
• X_i are distinct.

Sample Input 1

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

Sample Output 1

4
4
2
2
2
1

Initially, all cities are electrified.

• The 1-st event breaks Power Line 3 that connects Point 5 and Point 10.
  • Now City 5 is no longer electrified, while 4 cities remain electrified.
• The 2-nd event breaks Power Line 5 that connects Point 2 and Point 9.
• The 3-rd event breaks Power Line 8 that connects Point 3 and Point 6.
  • Now Cities 2 and 3 are no longer electrified, while 2 cities remain electrified.
• The 4-th event breaks Power Line 10 that connects Point 1 and Point 8.
• The 5-th event breaks Power Line 2 that connects Point 4 and Point 10.
• The 6-th event breaks Power Line 7 that connects Point 1 and Point 7.
  • Now City 1 is no longer electrified, while 1 city remains electrified.

Problem Statement

There are apple trees lined up on a number line, and N apples fall from the trees.
Specifically, for each 1\leq i\leq N, an apple falls at coordinate X_i at time T_i.

Takahashi has a basket with durability D and length W, and he can take the following action exactly once.

Choose positive integers S and L. He sets up the basket to cover the range L-0.5\leq x\leq L+W-0.5 at time S-0.5, and retrieves it at time S+D-0.5. He gets all the apples that fell into the range covered by the basket between the time it was set up and the time it was retrieved.

He cannot move the basket once it has been set up, nor can he set it up again once it has been retrieved.
Find the maximum number of apples that he can get.

Constraints

• 1 \leq N\leq 2\times 10^5
• 1 \leq D\leq 2\times 10^5
• 1 \leq W\leq 2\times 10^5
• 1 \leq T_i\leq 2\times 10^5
• 1 \leq X_i\leq 2\times 10^5
• All pairs (T_i,X_i) are different.
• All input values are integers.

Sample Input 1

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

Sample Output 1

5

If Takahashi chooses S=3 and L=2, he will set up the basket to cover the range 1.5\leq x\leq 4.5 from time 2.5 to 6.5. Then, he gets the following five apples:

• The apple that falls at coordinate X_2=4 at time T_2=3
• The apple that falls at coordinate X_3=4 at time T_3=6
• The apple that falls at coordinate X_4=2 at time T_4=5
• The apple that falls at coordinate X_5=2 at time T_5=4
• The apple that falls at coordinate X_6=3 at time T_6=4

There is no way to get six or more apples, so print 5.