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