Problem Statement

One day, tired from going to school, Takahashi wanted to know how many days there were until Saturday.
We know that the day was a weekday, and the name of the day of the week was S in English.
How many days were there until the first Saturday after that day (including Saturday but not the starting day)?

Constraints

• S is Monday, Tuesday, Wednesday, Thursday, or Friday.

Sample Input 1

Wednesday

Sample Output 1

3

It was Wednesday, so there were 3 days until the first Saturday after that day.

Sample Input 2

Monday

Sample Output 2

5

Problem Statement

Takahashi wants a beverage called AtCoder Drink in a restaurant. It can be ordered at a regular price of P yen.

He also has a discount coupon that allows him to order it at a lower price of Q yen. However, he must additionally order one of the restaurant's N dishes to use that coupon. For each i = 1, 2, \ldots, N, the price of the i-th dish is D_i yen.

Print the minimum total amount of money that he must pay to get the drink.

Constraints

• 1 \leq N \leq 100
• 1 \leq Q \lt P \leq 10^5
• 1 \leq D_i \leq 10^5
• All input values are integers.

Sample Input 1

3 100 50
60 20 40

Sample Output 1

70

If he uses the coupon and orders the second dish, he can get the drink by paying 50 yen for it and 20 yen for the dish, for a total of 70 yen, which is the minimum total payment needed.

Sample Input 2

3 100 50
60000 20000 40000

Sample Output 2

100

The total payment will be minimized by not using the coupon and paying the regular price of 100 yen.

Problem Statement

You are given a string S consisting of uppercase English letters and digits. Determine whether S satisfies the following condition.

• S is a concatenation of the following characters and string in the order listed.
  • An uppercase English letter
  • A string of length 6 that is a decimal representation of an integer between 100000 and 999999, inclusive
  • An uppercase English letter

Constraints

• S consists of uppercase English letters and digits.
• The length of S is between 1 and 10, inclusive.

Sample Input 1

Q142857Z

Sample Output 1

Yes

S is a concatenation of Q, 142857, and Z in this order.
Q and Z are uppercase English letters, and 142857 is a string of length 6 that is a decimal representation of an integer between 100000 and 999999, so S satisfies the condition.

Sample Input 2

AB912278C

Sample Output 2

No

AB is not an uppercase English letter, so S does not satisfy the condition.

Sample Input 3

X900000

Sample Output 3

No

The last character of S is not an uppercase English letter, so S does not satisfy the condition.

Sample Input 4

K012345K

Sample Output 4

No

012345 is not a string of length 6 that is a decimal representation of an integer between 100000 and 999999, so S does not satisfy the condition.

Problem Statement

We have a board with R rows running horizontally and C columns running vertically. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

You are given characters B_{i,j} representing the current states of (i,j). . represents an empty square; # represents a square with a wall; 1, 2,\dots, 9 represent a square with a bomb of power 1,2,\dots,9, respectively.

At the next moment, all bombs will explode simultaneously. When a bomb explodes, every square whose Manhattan distance from the square with the bomb is not greater than the power of the bomb will turn into an empty square. Here, the Manhattan distance from (r_1,c_1) to (r_2,c_2) is |r_1-r_2|+|c_1-c_2|.

Print the board after the explosions.

Constraints

• 1\leq R,C \leq 20
• R and C are integers.
• Each B_{i,j} is one of ., #, 1, 2, \dots, 9.

Sample Input 1

4 4
.1.#
###.
.#2.
#.##

Sample Output 1

...#
#...
....
#...

• The explosion of the bomb at (1,2) will turn the blue squares and purple squares in the above figure into empty squares.
• The explosion of the bomb at (3,3) will turn the red squares and purple squares in the above figure into empty squares.

As seen in this sample, the explosion ranges of bombs may overlap.

Sample Input 2

2 5
..#.#
###.#

Sample Output 2

..#.#
###.#

There may be no bombs.

Sample Input 3

2 3
11#
###

Sample Output 3

...
..#

Sample Input 4

4 6
#.#3#.
###.#.
##.###
#1..#.

Sample Output 4

......
#.....
#....#
....#.

Problem Statement

We have N cups of ice cream.
The flavor and deliciousness of the i-th cup are F_i and S_i, respectively (S_i is an even number).

You will choose and eat two of the N cups.
Your satisfaction here is defined as follows.

• Let s and t (s \ge t) be the deliciousness of the eaten cups.
  • If the two cups have different flavors, your satisfaction is \displaystyle s+t.
  • Otherwise, your satisfaction is \displaystyle s + \frac{t}{2}.

Find the maximum achievable satisfaction.

Constraints

• All input values are integers.
• 2 \le N \le 3 \times 10^5
• 1 \le F_i \le N
• 2 \le S_i \le 10^9
• S_i is even.

Sample Input 1

4
1 4
2 10
2 8
3 6

Sample Output 1

16

Consider eating the second and fourth cups.

• The second cup has a flavor of 2 and deliciousness of 10.
• The fourth cup has a flavor of 3 and deliciousness of 6.
• Since they have different flavors, your satisfaction is 10+6=16.

Thus, you can achieve the satisfaction of 16.
You cannot achieve a satisfaction greater than 16.

Sample Input 2

4
4 10
3 2
2 4
4 12

Sample Output 2

17

Consider eating the first and fourth cups.

• The first cup has a flavor of 4 and deliciousness of 10.
• The fourth cup has a flavor of 4 and deliciousness of 12.
• Since they have the same flavor, your satisfaction is 12+\frac{10}{2}=17.

Thus, you can achieve the satisfaction of 17.
You cannot achieve a satisfaction greater than 17.

Problem Statement

There is an N\times N grid with horizontal rows and vertical columns, where all squares are initially painted white. Let (i,j) denote the square at the i-th row and j-th column.

Takahashi has integers A and B, which are between 1 and N (inclusive). He will do the following operations.

• For every integer k such that \max(1-A,1-B)\leq k\leq \min(N-A,N-B), paint (A+k,B+k) black.
• For every integer k such that \max(1-A,B-N)\leq k\leq \min(N-A,B-1), paint (A+k,B-k) black.

In the grid after these operations, find the color of each square (i,j) such that P\leq i\leq Q and R\leq j\leq S.

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq A \leq N
• 1 \leq B \leq N
• 1 \leq P \leq Q \leq N
• 1 \leq R \leq S \leq N
• (Q-P+1)\times(S-R+1)\leq 3\times 10^5
• All values in input are integers.

Sample Input 1

5 3 2
1 5 1 5

Sample Output 1

...#.
#.#..
.#...
#.#..
...#.

The first operation paints the four squares (2,1), (3,2), (4,3), (5,4) black, and the second paints the four squares (4,1), (3,2), (2,3), (1,4) black.
Thus, the above output should be printed, since P=1, Q=5, R=1, S=5.

Sample Input 2

5 3 3
4 5 2 5

Sample Output 2

#.#.
...#

The operations paint the nine squares (1,1), (1,5), (2,2), (2,4), (3,3), (4,2), (4,4), (5,1), (5,5).
Thus, the above output should be printed, since P=4, Q=5, R=2, S=5.

Sample Input 3

1000000000000000000 999999999999999999 999999999999999999
999999999999999998 1000000000000000000 999999999999999998 1000000000000000000

Sample Output 3

#.#
.#.
#.#

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

Problem Statement

Given are a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) and a positive integer K.

For each i=K,K+1,\ldots,N, find the following.

• The K-th greatest value among the first i terms of P.

Constraints

• 1 \leq K \leq N \leq 5 \times 10^5
• (P_1,P_2,\ldots,P_N) is a permutation of (1,2,\ldots,N).
• All values in input are integers.

Sample Input 1

3 2
1 2 3

Sample Output 1

1
2

• The (K=) 2-nd greatest value among the first 2 terms of P, (P_1,P_2)=(1,2), is 1.
• The (K=) 2-nd greatest value among the first 3 terms of P, (P_1,P_2,P_3)=(1,2,3), is 2.

Sample Input 2

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

Sample Output 2

2
3
3
5
6
7
7

Problem Statement

10^{100} potatoes are coming from a conveyor belt one by one. The weights of the potatoes are described by a sequence W = (W_0, \dots, W_{N-1}) of length N: the weight of the i-th potato coming is W_{(i-1) \bmod N}, where (i-1) \bmod N denotes the remainder when i - 1 is divided by N.

Takahashi will prepare an empty box and then pack the potatoes in order, as follows.

• Pack the incoming potato into the box. If the total weight of the potatoes in the box is now X or greater, seal that box and prepare a new empty box.

You are given Q queries. In the i-th query (1 \leq i \leq Q), given a positive integer K_i, find the number of potatoes in the K_i-th box to be sealed. It can be proved that, under the Constraints of the problem, there will be at least K_i sealed boxes.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq X \leq 10^9
• 1 \leq W_i \leq 10^9 \, (0 \leq i \leq N - 1)
• 1 \leq K_i \leq 10^{12} \, (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

3 2 5
3 4 1
1
2

Sample Output 1

2
3

Before sealing the 2-nd box, Takahashi will do the following:

• Prepare an empty box.
• Pack the 1-st potato into the box. Now, the total weight of potatoes in the box is 3.
• Pack the 2-nd potato into the box. Now, the total weight of potatoes in the box is 3 + 4 = 7, which is not less than X = 5, so seal this box.
• Prepare a new empty box.
• Pack the 3-rd potato into the box. Now, the total weight of potatoes in the box is 1.
• Pack the 4-th potato into the box. Now, the total weight of potatoes in the box is 1 + 3 = 4.
• Pack the 5-th potato into the box. Now, the total weight of potatoes in the box is 1 + 3 + 4 = 8, which is not less than X = 5, so seal this box.

The 1-st box sealed contains 2 potatoes, and the 2-nd box sealed contains 3 potatoes.

Sample Input 2

10 5 20
5 8 5 9 8 7 4 4 8 2
1
1000
1000000
1000000000
1000000000000

Sample Output 2

4
5
5
5
5

Problem Statement

The Kingdom of AtCoder is composed of N towns and N-1 roads.
The towns are labeled as Town 1, Town 2, \dots, Town N. Similarly, the roads are labeled as Road 1, Road 2, \dots, Road N-1. Road i connects Towns A_i and B_i bidirectionally, and you have to pay the toll of C_i to go through it. For every pair of different towns (i, j), it is possible to go from Town A_i to Town B_j via the roads.

You are given a sequence D = (D_1, D_2, \dots, D_N), where D_i is the cost to do sightseeing in Town i. Let us define the travel cost E_{i,j} from Town i to Town j as the total toll incurred when going from Town i to Town j, plus D_{j}.

• More formally, E_{i,j} is defined as D_j + \displaystyle\sum_{l=0}^{k-1} c_l, where the shortest path between i and j is i = p_0, p_1, \dots, p_{k-1}, p_k = j and the toll for the road connecting Towns p_{l} and p_{l+1} is c_l.

For every i, find the maximum possible travel cost when traveling from Town i to another town.

• More formally, for every i, find \max_{1 \leq j \leq N, j \neq i} E_{i,j}.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq N (1 \leq i \leq N-1)
• 1 \leq B_i \leq N (1 \leq i \leq N-1)
• 1 \leq C_i \leq 10^9 (1 \leq i \leq N-1)
• 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
• It is possible to travel from Town i to Town j via some number of roads, for a pair of integers (i,j) such that 1 \leq i \lt j \leq N.
• All values in input are integers.

Sample Input 1

3
1 2 2
2 3 3
1 2 3

Sample Output 1

8
6
6

The value of E_{i,j} for every ordered pair of towns (i,j) is as follows.

• E_{1,2} = 2 + 2 = 4
• E_{1,3} = 5 + 3 = 8
• E_{2,1} = 2 + 1 = 3
• E_{2,3} = 3 + 3 = 6
• E_{3,1} = 5 + 1 = 6
• E_{3,2} = 3 + 2 = 5

Sample Input 2

6
1 2 3
1 3 1
1 4 4
1 5 1
1 6 5
9 2 6 5 3 100

Sample Output 2

105
108
106
109
106
14

Sample Input 3

6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
1 2 3 4 5 6

Sample Output 3

5000000006
4000000006
3000000006
3000000001
4000000001
5000000001