Problem Statement

Snuke has infinite number of square tiles and regular triangular tiles with side lengths 1. How many ways are there to form a regular dodecagon (12-sided polygon) with side lengths d using the tiles? Compute the answer modulo 998,244,353.

Formally speaking,

• He can use an arbitrary number of tiles.
• No two tiles may overlap.
• The union of the regions filled by the tiles must be a regular dodecagon without holes.
• We consider two ways to be the same if we can change one way to the other way by rotations and translations (but not reflections), such that each tile perfectly matches with a tile of the same type.

Constraints

• 1 \leq d \leq 10^6
• All values in the input are integers.

Sample Input 1

1

Sample Output 1

1

The following picture shows the only way.

Problem Statement

There are some number of bowling pins on a plane. Four people are observing the pins from different angles. Is it possible that one of the observers sees much more pins than the others?

Let's model the pins as a set of points on an xy-plane. The image below shows the positions of the four observers. Formally,

• For observer A, two pins overlap if their y-coordinates are the same.
• For observer B, two pins overlap if their values of (x-coordinate minus y-coordinate) are the same.
• For observer C, two pins overlap if their x-coordinates are the same.
• For observer D, two pins overlap if their values of (x-coordinate plus y-coordinate) are the same.

Let a, b, c, d be the number of pins the observers A, B, C, D see, respectively.

Construct any arrangement of bowling pins that satisfies the following constraints:

• d \geq 10 \cdot \max \{ a, b, c \}
• The number of pins is between 1 and 10^5, inclusive.
• The coordinates are integers between 0 and 10^9, inclusive.
• No two pins are placed at exactly the same place.

Sample Input 1

Sample Output 1

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

This sample output is provided for the sake of showing the output format and is not correct.

It matches the picture in the statement.

Here, d = 8 and a = b = c = 7. Nice try, but not enough to get AC.

Problem Statement

There is a square grid of dimensions 10^9 \times 10^9. The cells are numbered (1, 1) through (10^9, 10^9). Cell (i, j) is in the i-th row from the top, and the j-th column from the left. Initially, N cells (x_1, y_1), \ldots, (x_N, y_N) are black, and all other cells are white.

Snuke can perform the following operation an arbitrary number of times:

• Choose an integer x (1 \leq x \leq 10^9 - 1) and an integer y (1 \leq y \leq 10^9 - 2), and flip (black to white, white to black) the colors of the following six cells: (x, y), (x, y+1), (x, y+2), (x+1, y), (x+1, y+1), (x+1, y+2)

Compute the minimum possible number of black cells after the operations.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq x_i, y_i \leq 10^9
• (x_i, y_i) are pairwise distinct.
• All values in the input are integers.

Sample Input 1

9
1 2
1 3
2 1
2 3
2 4
3 2
3 3
3 4
4 2

Sample Output 1

3

In the diagram below, the j-th letter of the i-th string from the top represents the cell (i, j). # is black, . is white.

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

->

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

->

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

Problem Statement

In the following undirected graph, count the number of walks from S to S that pass through the edges ST, TU, UV, VS (in any direction) exactly a, b, c, d times, respectively, modulo 998,244,353.

Notes

A walk from S to S is a sequence of vertices v_0 = S, v_1, \ldots, v_k = S such that for each i (0 \leq i < k), there is an edge between v_i and v_{i+1}. Two walks are considered distinct if they are distinct as sequences.

Constraints

• 1 \leq a, b, c, d \leq 500,000
• All values in the input are integers.

Sample Input 1

2 2 2 2

Sample Output 1

10

There are 10 walks that satisfy the condition. One example of such a walk is S \rightarrow T \rightarrow U \rightarrow V \rightarrow U \rightarrow T \rightarrow S \rightarrow V \rightarrow S.

Sample Input 2

1 2 3 4

Sample Output 2

0

Sample Input 3

470000 480000 490000 500000

Sample Output 3

712808431

Problem Statement

Initially, N points (x_1, y_1), \ldots, (x_N, y_N) are plotted on a plane. Snuke is allowed to perform the following operation an arbitrary finite number of times:

• Choose two points that are already plotted, and plot the middle point of the two chosen points (if the middle point hasn't been plotted yet). The coordinates of the middle point don't necessarily have to be integers.

After he finish performing operations, his score is the number of plotted points with integer coordinates (including the initial points). Compute the maximum score he can get.

Constraints

• 3 \leq N \leq 100
• 0 \leq x_i, y_i \leq 10^9
• No three points are on the same line.
• All values in the input are integers.

Sample Input 1

4
0 0
0 2
2 0
2 2

Sample Output 1

9

One possible way to achieve the maximum score is as follows:

• Initially, four points (0, 0), (0, 2), (2, 0), (2, 2) are plotted.
• Plot (0, 1): the middle point of (0, 0) and (0, 2).
• Plot (0, 0.5): the middle point of (0, 0) and (0, 1).
• Plot (1, 0): the middle point of (0, 0) and (2, 0).
• Plot (1, 1): the middle point of (0, 0) and (2, 2).
• Plot (1, 2): the middle point of (0, 2) and (2, 2).
• Plot (2, 1): the middle point of (2, 0) and (2, 2).
• Now we have 10 points: (0, 0), (0, 0.5), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2). 9 of them have integer coordinates, so the score is 9.

Sample Input 2

4
0 0
0 3
3 0
3 3

Sample Output 2

4

We can prove that, besides the initial points, he can't plot any points with integer coordinates.

Problem Statement

You have two sandglasses: a sandglass that can measure 1 second, and a sandglass that can measure \sqrt{2} seconds. Is it possible to measure x + y \sqrt{2} seconds using them?

Let's formalize the statement. We have two sandglasses named A and B. Each sandglass has two bulbs, and the bulbs may contain sand. We can place each sandglass in one of the three states: two vertical states (one of the bulbs is placed on top of the other, and in case the top bulb contains sand, the sand in the top bulb keeps falling into the bottom bulb at the speed of one gram per second.) and one horizontal state (the sand does not move.)

The sandglass A contains 1 gram of sand and the sandglass B contains \sqrt{2} grams of sand. Thus, when sandglass A is vertically placed and all sand is in the top bulb, it takes 1 second until all sand falls into the bottom bulb. Similarly, this time is \sqrt{2} seconds for sandglass B.

Initially, both A and B are vertically placed, and all sand is in the bottom bulb. You are not allowed to touch anything before Snuke shouts. When an event (described below) happens exactly t seconds after Snuke shouts, we say that we can measure t seconds.

We say that an event happens when one of the following happens:

• Snuke shouts.
• The sand in a sandglass in a vertical state has just stopped falling down.

When an event happens, we can perform (an arbitrary number of) the following operation in negligible time:

• Choose a sandglasses, and change its state.

For example, we can measure -1 + 2 \sqrt{2} seconds as follows:

• At time 0, Snuke shouts. Turn both A and B upside down.
• At time 1, an event happens: the sand in A stops falling down. Turn A upside down again (and leave B as it is).
• At time \sqrt{2}, an event happens: the sand in B stops falling down. Turn A upside down again, and leave B in the horizontal state.
• At time -1 + 2 \sqrt{2}, an event happens: the sand in A stops falling down.

You are given Q numbers of the form x_i + y_i \sqrt{2}. Solve the problem above for each given number.

Constraints

• 1 \leq Q \leq 10^5
• -10^9 \leq x_i, y_i \leq 10^9
• x_i + y_i \sqrt{2} > 0
• All values in the input are integers.

Sample Input 1

3
-1 2
2020 1227
2 -1

Sample Output 1

Yes
Yes
No