Problem Statement

You are given positive integers N and K, and a sequence of length N, A=(A_1,A_2,\ldots,A_N).

Extract all elements of A that are multiples of K, divide them by K, and print the quotients.

Constraints

• 1\leq N,K\leq 100
• 1\leq A_1 < A_2 < \ldots < A_N \leq 100
• A has at least one multiple of K.
• All given numbers are integers.

Sample Input 1

5 2
2 5 6 7 10

Sample Output 1

1 3 5

The multiples of 2 among the elements in A are 2, 6, and 10. Divide them by 2 to get 1, 3, and 5, and print them in ascending order with spaces in between.

Sample Input 2

3 1
3 4 7

Sample Output 2

3 4 7

Sample Input 3

5 10
50 51 54 60 65

Sample Output 3

5 6

Problem Statement

Given a length-3 string S consisting of uppercase English letters, print Yes if S equals one of ACE, BDF, CEG, DFA, EGB, FAC, and GBD; print No otherwise.

Constraints

• S is a length-3 string consisting of uppercase English letters.

Sample Input 1

ABC

Sample Output 1

No

When S = ABC, S does not equal any of ACE, BDF, CEG, DFA, EGB, FAC, and GBD, so No should be printed.

Sample Input 2

FAC

Sample Output 2

Yes

Sample Input 3

XYX

Sample Output 3

No

Problem Statement

You are given strings S and T consisting of lowercase and uppercase English letters.

Determine whether the string S satisfies the following condition:

• Every uppercase letter in S that is not at the beginning is immediately preceded by a character contained in T. More formally, for all integers i such that 2 \leq i \leq |S|, if the i-th character of S is uppercase, then the (i-1)-th character of S is contained in T.

Constraints

• Each of S and T is a string consisting of lowercase and uppercase English letters with length between 1 and 100, inclusive.

Sample Input 1

AtCoder
Total

Sample Output 1

Yes

The only uppercase letter in S that is not at the beginning is the 3rd character C. The immediately preceding character t is contained in T, so output Yes.

Sample Input 2

aBCdE
abcdcba

Sample Output 2

No

The 3rd character of S is the uppercase letter C, and its immediately preceding character is B, but B is not contained in T.

Sample Input 3

abcde
XYZ

Sample Output 3

Yes

Problem Statement

There is a grid of 64 squares with 8 rows and 8 columns. Let (i,j) denote the square at the i-th row from the top (1\leq i\leq8) and j-th column from the left (1\leq j\leq8).

Each square is either empty or has a piece placed on it. The state of the squares is represented by a sequence (S_1,S_2,S_3,\ldots,S_8) of 8 strings of length 8. Square (i,j) (1\leq i\leq8,1\leq j\leq8) is empty if the j-th character of S_i is ., and has a piece if it is #.

You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.

A piece placed on square (i,j) can capture pieces that satisfy either of the following conditions:

• Placed on a square in row i
• Placed on a square in column j

For example, a piece placed on square (4,4) can capture pieces placed on the squares shown in blue in the following figure:

How many squares can you place your piece on?

Constraints

• Each S_i is a string of length 8 consisting of . and # (1\leq i\leq 8).

Sample Input 1

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

Sample Output 1

4

The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece without it being captured on 4 squares: square (6,6), square (6,7), square (7,6), and square (7,7).

Sample Input 2

........
........
........
........
........
........
........
........

Sample Output 2

64

There may be no pieces on the grid.

Sample Input 3

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

Sample Output 3

4

Problem Statement

Consider a two-dimensional coordinate plane, where the x-axis is oriented to the right, and the y-axis is oriented upward.

In this plane, there is a quadrilateral without self-intersection.
The coordinates of the four vertices are (A_x,A_y), (B_x,B_y), (C_x,C_y), and (D_x,D_y), in counter-clockwise order.

Determine whether this quadrilateral is convex.

Here, a quadrilateral is convex if and only if all four interior angles are less than 180 degrees.

Constraints

• -100 \leq A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y \leq 100
• All values in input are integers.
• The given four points are the four vertices of a quadrilateral in counter-clockwise order.
• The quadrilateral formed by the given four points has no self-intersection and is non-degenerate. That is,
  • no two vertices are at the same coordinates;
  • no three vertices are colinear; and
  • no two edges that are not adjacent have a common point.

Sample Input 1

0 0
1 0
1 1
0 1

Sample Output 1

Yes

The given quadrilateral is a square, whose four interior angles are all 90 degrees. Thus, this quadrilateral is convex.

Sample Input 2

0 0
1 1
-1 0
1 -1

Sample Output 2

No

The angle A is 270 degrees. Thus, this quadrilateral is not convex.

Problem Statement

A string T of length 3 consisting of uppercase English letters is an airport code for a string S of lowercase English letters if and only if T can be derived from S by one of the following methods:

• Take a subsequence of length 3 from S (not necessarily contiguous) and convert it to uppercase letters to form T.
• Take a subsequence of length 2 from S (not necessarily contiguous), convert it to uppercase letters, and append X to the end to form T.

Given strings S and T, determine if T is an airport code for S.

Constraints

• S is a string of lowercase English letters with a length between 3 and 10^5, inclusive.
• T is a string of uppercase English letters with a length of 3.

Sample Input 1

narita
NRT

Sample Output 1

Yes

The subsequence nrt of narita, when converted to uppercase, forms the string NRT, which is an airport code for narita.

Sample Input 2

losangeles
LAX

Sample Output 2

Yes

The subsequence la of losangeles, when converted to uppercase and appended with X, forms the string LAX, which is an airport code for losangeles.

Sample Input 3

snuke
RNG

Sample Output 3

No

Problem Statement

There are N villages on a number line. The i-th village is located at coordinate X_i, and has P_i villagers.

Answer Q queries. The i-th query is in the following format:

• Given integers L_i and R_i, find the total number of villagers living in villages located between coordinates L_i and R_i, inclusive.

Constraints

• 1\leq N,Q\leq 2\times 10^5
• -10^9\leq X_1 < X_2 < \ldots < X_N \leq 10^9
• 1\leq P_i\leq 10^9
• -10^9\leq L_i \leq R_i \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
5
10
0

Consider the first query. The villages between coordinates 1 and 1 are the village at coordinate 1, with 1 villager. Hence, the answer is 1.

Consider the second query. The villages between coordinates 2 and 6 are the villages at coordinates 3 and 5, with 2 and 3 villagers, respectively. Hence, the answer is 2+3=5.

Sample Input 2

7
-10 -5 -3 -1 0 1 4
2 5 6 5 2 1 7
8
-7 7
-1 5
-10 -4
-8 10
-5 0
-10 5
-8 7
-8 -3

Sample Output 2

26
15
7
26
18
28
26
11

Problem Statement

You are given a sequence of non-negative integers A = (A_1,\dots,A_{2N}) of length 2N.

Define the score of a parenthesis sequence s of length 2N as follows:

• For every position i where the i-th character of s is ), set A_i to 0, then take the sum of all elements of A.

Find the maximum possible score of a correct parenthesis sequence of length 2N.

You are given T test cases; solve each.

Constraints

• 1 \le T \le 500
• 1 \le N \le 2 \times 10^{5}
• For each input file, the sum of N over all test cases is at most 2 \times 10^{5}.
• 0 \le A_i \le 10^{9} (1 \le i \le 2N)
• All input values are integers.

Sample Input 1

2
3
400
500
200
100
300
600
6
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000

Sample Output 1

1200
6000000000

In the first test case, choosing the correct parenthesis string (())() gives a score of 400+500+0+0+300+0=1200.

No correct parenthesis string yields a higher score, so the answer is 1200.

Note that, as in the second test case of this sample, the answer may exceed the 32-bit integer range.

Problem Statement

Tiles are laid out on a coordinate plane. There are two types of tiles: small tiles of size 1\times1 and large tiles of size K\times K, laid out according to the following rules:

• For each pair of integers (i,j), the square \lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace is contained within either one small tile or one large tile.
  • If \left\lfloor\dfrac iK\right\rfloor+\left\lfloor\dfrac jK\right\rfloor is even, it is contained within a small tile.
  • Otherwise, it is contained within a large tile.

Tiles include their boundaries, and no two different tiles have a positive area of intersection.

For example, when K=3, tiles are laid out as follows:

Takahashi starts at the point (S_x+0.5,S_y+0.5) on the coordinate plane.

He can repeat the following movement any number of times:

• Choose a direction (up, down, left, or right) and a positive integer n. Move n units in that direction.

Each time he crosses from one tile to another, he must pay a toll of 1.

Determine the minimum toll Takahashi must pay to reach the point (T_x+0.5,T_y+0.5).

Constraints

• 1\leq K\leq10^{16}
• 0\leq S_x\leq2\times10^{16}
• 0\leq S_y\leq2\times10^{16}
• 0\leq T_x\leq2\times10^{16}
• 0\leq T_y\leq2\times10^{16}
• All input values are integers.

Sample Input 1

3
7 2
1 6

Sample Output 1

5

For example, he can move as follows, paying a toll of 5.

• Move up by 3. Pay a toll of 1.
• Move left by 2. Pay a toll of 1.
• Move up by 1. Pay a toll of 1.
• Move left by 4. Pay a toll of 2.

The toll paid cannot be 4 or less, so print 5.

Sample Input 2

1
41 42
13 56

Sample Output 2

42

When he moves the shortest distance, he will always pay a toll of 42.

The toll paid cannot be 41 or less, so print 42.

Sample Input 3

100
100 99
199 1

Sample Output 3

0

There are cases where no toll needs to be paid.

Sample Input 4

96929423
5105216413055191 10822465733465225
1543712011036057 14412421458305526

Sample Output 4

79154049