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

We have HW cards arranged in a matrix with H rows and W columns.
For each i=1, \ldots, N, the card at the A_i-th row from the top and B_i-th column from the left has a number i written on it. The other HW-N cards have nothing written on them.

We will repeat the following two kinds of operations on these cards as long as we can.

• If there is a row without a numbered card, remove all the cards in that row and fill the gap by shifting the remaining cards upward.
• If there is a column without a numbered card, remove all the cards in that column and fill the gap by shifting the remaining cards to the left.

Find the position of each numbered card after the end of the process above. It can be proved that these positions are uniquely determined without depending on the order in which the operations are done.

Constraints

• 1 \leq H,W \leq 10^9
• 1 \leq N \leq \min(10^5,HW)
• 1 \leq A_i \leq H
• 1 \leq B_i \leq W
• All pairs (A_i,B_i) are distinct.
• All values in input are integers.

Sample Input 1

4 5 2
3 2
2 5

Sample Output 1

2 1
1 2

Let * represent a card with nothing written on it. The initial arrangement of cards is:

*****
****2
*1***
*****

After the end of the process, they will be arranged as follows:

*2
1*

Here, the card with 1 is at the 2-nd row from the top and 1-st column from the left, and the card with 2 is at the 1-st row from the top and 2-nd column from the left.

Sample Input 2

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

Sample Output 2

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

Problem Statement

A function f(x) defined for non-negative integers x satisfies the following conditions.

• f(0) = 1.
• f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor) for any positive integer k.

Here, \lfloor A \rfloor denotes the value of A rounded down to an integer.

Find f(N).

Constraints

• N is an integer satisfying 0 \le N \le 10^{18}.

Sample Input 1

2

Sample Output 1

3

We have f(2) = f(\lfloor \frac{2}{2}\rfloor) + f(\lfloor \frac{2}{3}\rfloor) = f(1) + f(0) =(f(\lfloor \frac{1}{2}\rfloor) + f(\lfloor \frac{1}{3}\rfloor)) + f(0) =(f(0)+f(0)) + f(0)= 3.

Sample Input 2

0

Sample Output 2

1

Sample Input 3

100

Sample Output 3

55

Problem Statement

Given integers A, X, and M, find \displaystyle \sum_{i = 0}^{X-1} A^i, modulo M.

Constraints

• 1 \leq A, M \leq 10^9
• 1 \leq X \leq 10^{12}
• All values in the input are integers.

Sample Input 1

3 4 7

Sample Output 1

5

3^0 + 3^1 + 3^2 + 3^3 = 40, which equals 5 modulo 7, so 5 should be printed.

Sample Input 2

8 10 9

Sample Output 2

0

Sample Input 3

1000000000 1000000000000 998244353

Sample Output 3

919667211

Problem Statement

You are given a positive integer N and sequences of N positive integers each: A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N).

We have an N \times N grid. The square at the i-th row from the top and the j-th column from the left is called the square (i,j). For each pair of integers (i,j) such that 1 \le i,j \le N, the square (i,j) has the integer A_i + B_j written on it. Process Q queries of the following form.

• You are given a quadruple of integers h_1,h_2,w_1,w_2 such that 1 \le h_1 \le h_2 \le N,1 \le w_1 \le w_2 \le N. Find the greatest common divisor of the integers contained in the rectangle region whose top-left and bottom-right corners are (h_1,w_1) and (h_2,w_2), respectively.

Constraints

• 1 \le N,Q \le 2 \times 10^5
• 1 \le A_i,B_i \le 10^9
• 1 \le h_1 \le h_2 \le N
• 1 \le w_1 \le w_2 \le N
• All values in input are integers.

Sample Input 1

3 5
3 5 2
8 1 3
1 2 2 3
1 3 1 3
1 1 1 1
2 2 2 2
3 3 1 1

Sample Output 1

2
1
11
6
10

Let C_{i,j} denote the integer on the square (i,j).

For the 1-st query, we have C_{1,2}=4,C_{1,3}=6,C_{2,2}=6,C_{2,3}=8, so the answer is their greatest common divisor, which is 2.

Sample Input 2

1 1
9
100
1 1 1 1

Sample Output 2

109