Problem Statement

AtCoder Regular Contest (ARC) currently has two divisions: Div. 1 and Div. 2. In ARC Div. 1, participants whose rating is between 1600 and 2999, inclusive, are rated. In ARC Div. 2, participants whose rating is between 1200 and 2399, inclusive, are rated.

You are given positive integers R and X.

Determine whether a person with rating R is rated in ARC Div. X.

Constraints

• 1 \le R \le 4229
• 1 \le X \le 2
• All input values are integers.

Sample Input 1

2000 1

Sample Output 1

Yes

Because 2000 lies between 1600 and 2999, a person with rating 2000 is rated in ARC Div. 1.

Sample Input 2

1000 1

Sample Output 2

No

Because 1000 is less than 1600, a person with rating 1000 is not rated in ARC Div. 1.

Sample Input 3

1500 2

Sample Output 3

Yes

Because 1500 lies between 1200 and 2399, a person with rating 1500 is rated in ARC Div. 2.

Sample Input 4

2800 2

Sample Output 4

No

Because 2800 exceeds 2399, a person with rating 2800 is not rated in ARC Div. 2.

Problem Statement

Print all non-negative integers less than or equal to N in descending order.

Constraints

• 1 \leq N \leq 100
• N is an integer.

Sample Input 1

3

Sample Output 1

3
2
1
0

We have four non-negative integers less than or equal to 3, which are 0, 1, 2, and 3.
To print them in descending order, print 3 in the first line, 2 in the second, 1 in the third, and 0 in the fourth.

Sample Input 2

22

Sample Output 2

22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

Problem Statement

You are trying to implement collision detection in a 3D game.

In a 3-dimensional space, let C(a,b,c,d,e,f) denote the cuboid with a diagonal connecting (a,b,c) and (d,e,f), and with all faces parallel to the xy-plane, yz-plane, or zx-plane.
(This definition uniquely determines C(a,b,c,d,e,f).)

Given two cuboids C(a,b,c,d,e,f) and C(g,h,i,j,k,l), determine whether their intersection has a positive volume.

Constraints

• 0 \leq a < d \leq 1000
• 0 \leq b < e \leq 1000
• 0 \leq c < f \leq 1000
• 0 \leq g < j \leq 1000
• 0 \leq h < k \leq 1000
• 0 \leq i < l \leq 1000
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes

The positional relationship of the two cuboids is shown in the figure below, and their intersection has a volume of 8.

Sample Input 2

0 0 0 2 2 2
0 0 2 2 2 4

Sample Output 2

No

The two cuboids touch at a face, where the volume of the intersection is 0.

Sample Input 3

0 0 0 1000 1000 1000
10 10 10 100 100 100

Sample Output 3

Yes

Problem Statement

Locate a piece on a chessboard.

We have a grid with 8 rows and 8 columns of squares. Each of the squares has a 2-character name determined as follows.

• The first character of the name of a square in the 1-st column from the left is a. Similarly, the first character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th column from the left is b, c, d, e, f, g, h, respectively.
• The second character of the name of a square in the 1-st row from the bottom is 1. Similarly, the second character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th row from the bottom is 2, 3, 4, 5, 6, 7, 8, respectively.

For instance, the bottom-left square is named a1, the bottom-right square is named h1, and the top-right square is named h8.

You are given 8 strings S_1,\ldots,S_8, each of length 8, representing the state of the grid.
The j-th character of S_i is * if the square at the i-th row from the top and j-th column from the left has a piece on it, and . otherwise. The character * occurs exactly once among S_1,\ldots,S_8. Find the name of the square that has a piece on it.

Constraints

• S_i is a string of length 8 consisting of . and*.
• The character * occurs exactly once among S_1,\ldots,S_8.

Sample Input 1

........
........
........
........
........
........
........
*.......

Sample Output 1

a1

As explained in the problem statement, the bottom-left square is named a1.

Sample Input 2

........
........
........
........
........
.*......
........
........

Sample Output 2

b3

Problem Statement

Takahashi is planning an N-day train trip.
For each day, he can pay the regular fare or use a one-day pass.

Here, for 1\leq i\leq N, the regular fare for the i-th day of the trip is F_i yen.
On the other hand, a batch of D one-day passes is sold for P yen. You can buy as many passes as you want, but only in units of D.
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.

Find the minimum possible total cost for the N-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.

Constraints

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

Sample Input 1

5 2 10
7 1 6 3 6

Sample Output 1

20

If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be (10\times 1)+(0+1+0+3+6)=20, which is the minimum cost needed.
Thus, print 20.

Sample Input 2

3 1 10
1 2 3

Sample Output 2

6

The minimum cost is achieved by paying the regular fare for all three days.

Sample Input 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

The minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.
Note that the answer may not fit into a 32-bit integer type.