Problem Statement

There is a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left.
Find the number of squares that share a side with Square (R, C).

Here, two squares (a,b) and (c,d) are said to share a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Constraints

• All values in input are integers.
• 1 \le R \le H \le 10
• 1 \le C \le W \le 10

Sample Input 1

3 4
2 2

Sample Output 1

4

We will describe Sample Inputs/Outputs 1,2, and 3 at once below Sample Output 3.

Sample Input 2

3 4
1 3

Sample Output 2

3

Sample Input 3

3 4
3 4

Sample Output 3

2

When H=3 and W=4, the grid looks as follows.

• For Sample Input 1, there are 4 squares adjacent to Square (2,2).
• For Sample Input 2, there are 3 squares adjacent to Square (1,3).
• For Sample Input 3, there are 2 squares adjacent to Square (3,4).

Sample Input 4

1 10
1 5

Sample Output 4

2

Sample Input 5

8 1
8 1

Sample Output 5

1

Sample Input 6

1 1
1 1

Sample Output 6

0

Problem Statement

Tiles are aligned in N horizontal rows and N vertical columns. Each tile has a grid with A horizontal rows and B vertical columns. On the whole, the tiles form a grid X with (A\times N) horizontal rows and (B\times N) vertical columns.
For 1\leq i,j \leq N, Tile (i,j) denotes the tile at the i-th row from the top and the j-th column from the left.

Each square of X is painted as follows.

• Each tile is either a white tile or a black tile.
• Every square in a white tile is painted white; every square in a black tile is painted black.
• Tile (1,1) is a white tile.
• Two tiles sharing a side have different colors. Here, Tile (a,b) and Tile (c,d) are said to be sharing a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Print the grid X in the format specified in the Output section.

Constraints

• 1 \leq N,A,B \leq 10
• All values in input are integers.

Sample Input 1

4 3 2

Sample Output 1

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

Sample Input 2

5 1 5

Sample Output 2

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

Sample Input 3

4 4 1

Sample Output 3

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

Sample Input 4

1 4 4

Sample Output 4

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

Problem Statement

N balls are lined up in a row from left to right. Initially, the i-th (1 \leq i \leq N) ball from the left has an integer i written on it.

Takahashi has performed Q operations. The i-th (1 \leq i \leq Q) operation was as follows.

• Swap the ball with the integer x_i written on it with the next ball to the right. If the ball with the integer x_i written on it was originally the rightmost ball, swap it with the next ball to the left instead.

Let a_i be the integer written on the i-th (1 \leq i \leq N) ball after the operations. Find a_1,\ldots,a_N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq x_i \leq N
• All values in input are integers.

Sample Input 1

5 5
1
2
3
4
5

Sample Output 1

1 2 3 5 4

The operations are performed as follows.

• Swap the ball with 1 written on it with the next ball to the right. Now, the balls have integers 2,1,3,4,5 written on them, from left to right.
• Swap the ball with 2 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
• Swap the ball with 3 written on it with the next ball to the right. Now, the balls have integers 1,2,4,3,5 written on them, from left to right.
• Swap the ball with 4 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
• Swap the ball with 5 written on it with the next ball to the left, since it is the rightmost ball. Now, the balls have integers 1,2,3,5,4 written on them, from left to right.

Sample Input 2

7 7
7
7
7
7
7
7
7

Sample Output 2

1 2 3 4 5 7 6

Sample Input 3

10 6
1
5
2
9
6
6

Sample Output 3

1 2 3 4 5 7 6 8 10 9

Problem Statement

Let us regard an integer k as "similar to 250" if the following condition is satisfied:

• k is represented as k=p \times q^3 with primes p<q.

How many integers less than or equal to N are "similar to 250"?

Constraints

• N is an integer between 1 and 10^{18} (inclusive)

Sample Input 1

250

Sample Output 1

2

• 54 = 2 \times 3^3 is "similar to 250".
• 250 = 2 \times 5^3 is "similar to 250".

The two integers above are all the integers "similar to 250".

Sample Input 2

1

Sample Output 2

0

Sample Input 3

123456789012345

Sample Output 3

226863

Problem Statement

You are given integer sequences A = (a_1,\ldots,a_N) and B = (b_1,\ldots,b_N), each of length N.

For i=1,...,Q, answer the query in the following format.

• If the set of values contained in the first x_i terms of A, (a_1,\ldots,a_{x_i}), and the set of values contained in the first y_i terms of B, (b_1,\ldots,b_{y_i}), are equal, then print Yes; otherwise, print No.

Constraints

• 1 \leq N,Q \leq 2 \times 10^5
• 1 \leq a_i,b_i \leq 10^9
• 1 \leq x_i,y_i \leq N
• All values in input are integers.

Sample Input 1

5
1 2 3 4 5
1 2 2 4 3
7
1 1
2 2
2 3
3 3
4 4
4 5
5 5

Sample Output 1

Yes
Yes
Yes
No
No
Yes
No

Note that sets are a concept where it matters only whether each value is contained or not.
For the 3-rd query, the first 2 terms of A contain one 1 and one 2, while the first 3 terms of B contain one 1 and two 2's. However, the sets of values contained in the segments are both \{ 1,2 \}, which are equal.
Also, for the 6-th query, the values appear in different orders, but they are still equal as sets.

Problem Statement

ABC 250 is a commemorable quarter milestone for Takahashi, who aims to hold ABC 1000, so he is going to celebrate this contest by eating as close to 1/4 of a pizza he bought as possible.

The pizza that Takahashi bought has a planar shape of convex N-gon. When the pizza is placed on an xy-plane, the i-th vertex has coordinates (X_i, Y_i).

Takahashi has decided to cut and eat the pizza as follows.

• First, Takahashi chooses two non-adjacent vertices from the vertices of the pizza and makes a cut with a knife along the line passing through those two points, dividing the pizza into two pieces.
• Then, he chooses one of the pieces at his choice and eats it.

Let a be the quarter (=1/4) of the area of the pizza that Takahashi bought, and b be the area of the piece of pizza that Takahashi eats. Find the minimum possible value of 8 \times |a-b|. We can prove that this value is always an integer.

Constraints

• All values in input are integers.
• 4 \le N \le 10^5
• |X_i|, |Y_i| \le 4 \times 10^8
• The given points are the vertices of a convex N-gon in the counterclockwise order.

Sample Input 1

5
3 0
2 3
-1 3
-3 1
-1 -1

Sample Output 1

1

Suppose that he makes a cut along the line passing through the 3-rd and the 5-th vertex and eats the piece containing the 4-th vertex.
Then, a=\frac{33}{2} \times \frac{1}{4} = \frac{33}{8}, b=4, and 8 \times |a-b|=1, which is minimum possible.

Sample Input 2

4
400000000 400000000
-400000000 400000000
-400000000 -400000000
400000000 -400000000

Sample Output 2

1280000000000000000

Sample Input 3

6
-816 222
-801 -757
-165 -411
733 131
835 711
-374 979

Sample Output 3

157889

Problem Statement

You are going to trade stocks of Company X for the next N days.

As a precognitive, you know that the stock price on the i-th day of trading will be P_i yen (the currency in Japan) per unit.

Every day, you can choose to do exactly one of the following.

• Buy one unit of stock for P_i yen.
  • You will obtain one unit of stock and your money will decrease by P_i yen.
• Sell one unit of stock for P_i yen.
  • You will lose one unit of stock and your money will increase by P_i yen.
• Do nothing.

You initially have 10^{100} yen, so you will never be short of money.

Find the maximum possible amount of money you will have gained when the N-th day has ended.
Even if you still possess some amount of stocks of Company X when the N-th day has ended, it is considered that they are worth 0 yen.

Constraints

• All values in input are integers.
• 1 \le N \le 2 \times 10^5
• 1 \le P_i \le 10^9

Sample Input 1

8
2 5 4 3 7 1 8 6

Sample Output 1

16

By acting as follows, your money will increase by 16 yen, which is the maximum possible.

• On the 1-th day, you buy 1 unit of stock. You now have 1 unit of stock, and your money has increased by -2 yen so far.
• On the 2-nd day, you sell 1 unit of stock. You now have 0 units of stocks, and your money has increased by 3 yen so far.
• On the 3-rd day, you buy 1 unit of stock. You now have 1 unit of stock, and your money has increased by -1 yen so far.
• On the 4-th day, you buy 1 unit of stock. You now have 2 units of stocks, and your money has increased by -4 yen so far.
• On the 5-th day, you sell 1 unit of stock. You now have 1 unit of stock, and your money has increased by 3 yen so far.
• On the 6-th day, you buy 1 unit of stock. You now have 2 units of stocks, and your money has increased by 2 yen so far.
• On the 7-th day, you sell 1 unit of stock. You now have 1 unit of stock, and your money has increased by 10 yen so far.
• On the 8-th day, you sell 1 unit of stock. You now have 0 units of stocks, and your money has increased by 16 yen so far.

Sample Input 2

5
10000 1000 100 10 1

Sample Output 2

0

Sample Input 3

15
300 1 4000 1 50000 900000000 20 600000 50000 300 50000 80000000 900000000 7000000 900000000

Sample Output 3

2787595378

Problem Statement

There are N points numbered 1 through N, and M roads. The i-th (1 \leq i \leq M) road connects Point a_i and Point b_i bidirectionally and requires c_i minutes to pass through. One can travel from any point to any other point using some number of roads. There is a house on Points 1,\ldots, K.

For i=1,\ldots,Q, solve the following problem.

Takahashi is currently at the house at Point x_i and wants to travel to the house at Point y_i.
Once t_i minutes have passed since his last sleep, he cannot continue moving anymore.
He can get sleep only at a point with a house, but he may do so any number of times.
If he can travel from Point x_i to Point y_i, print Yes; otherwise, print No.

Constraints

• 2 \leq K \leq N \leq 2 \times 10^5
• N-1 \leq M \leq \min (2 \times 10^5, \frac{N(N-1)}{2})
• 1 \leq a_i \lt b_i \leq N
• If i \neq j, then (a_i,b_i) \neq (a_j,b_j).
• 1 \leq c_i \leq 10^9
• One can travel from any point to any other point using some number of roads.
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq x_i \lt y_i \leq K
• 1 \leq t_1 \leq \ldots \leq t_Q \leq 10^{15}
• All values in input are integers.

Sample Input 1

6 6 3
1 4 1
4 6 4
2 5 2
3 5 3
5 6 5
1 2 15
3
2 3 4
2 3 5
1 3 12

Sample Output 1

No
Yes
Yes

In the 3-rd problem, it takes no less than 13 minutes from Point 1 to reach Point 3 directly. However, he can first travel to Point 2 in 12 minutes, get sleep in the house there, and then travel to Point 3. Thus, the answer is Yes.