実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
高橋くんは満月が好きです。
今日を 1 日目とすると、今日以降で満月を見られる最初の日は M 日目です。以後は P 日ごと、つまり M+P 日目、M+2P 日目、\ldots に満月を見られます。
1 日目から N 日目まで（両端を含む）の中で、高橋くんが満月を見られる日の数を求めてください。
制約
- 1\leq N\leq 2\times 10^5
- 1\leq M \leq P \leq 2\times 10^5
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M P
出力
答えを整数として出力せよ。
入力例 1
13 3 5
出力例 1
3
満月を見られる日は、3 日目、8 日目、13 日目、18 日目、\ldots です。
1 日目から 13 日目までの中で高橋くんが満月を見られる日は、3 日目、8 日目、13 日目の 3 個です。
入力例 2
5 6 6
出力例 2
0
高橋くんが満月を見られる日が存在しない場合もあります。
入力例 3
200000 314 318
出力例 3
628
Score : 100 points
Problem Statement
Takahashi likes full moons.
Let today be day 1. The first day on or after today on which he can see a full moon is day M. After that, he can see a full moon every P days, that is, on day M+P, day M+2P, and so on.
Find the number of days between day 1 and day N, inclusive, on which he can see a full moon.
Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq M \leq P \leq 2\times 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M P
Output
Print the answer as an integer.
Sample Input 1
13 3 5
Sample Output 1
3
He can see a full moon on day 3, 8, 13, 18, and so on.
From day 1 to 13, he can see a full moon on three days: day 3, 8, and 13.
Sample Input 2
5 6 6
Sample Output 2
0
There may be no days he can see a full moon.
Sample Input 3
200000 314 318
Sample Output 3
628
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
(1,2,…,N) を並び替えた数列 P と整数 X が与えられます。 数列 P の i 番目の項の値は P_i です。 P_k = X を満たす k を出力してください。
制約
- 1 \leq N \leq 100
- 1 \leq X \leq N
- P は (1,2,…,N) を並び替えてできる数列
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X P_1 P_2 \ldots P_N
出力
答えを出力せよ。
入力例 1
4 3 2 3 1 4
出力例 1
2
P = (2,3,1,4) なので、P_2 = 3 です。したがって、2 を出力します。
入力例 2
5 2 3 5 1 4 2
出力例 2
5
入力例 3
6 6 1 2 3 4 5 6
出力例 3
6
Score : 100 points
Problem Statement
You are given a sequence P that is a permutation of (1,2,…,N), and an integer X. The i-th term of P has a value of P_i. Print k such that P_k = X.
Constraints
- 1 \leq N \leq 100
- 1 \leq X \leq N
- P is a permutation of (1,2,…,N).
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N X P_1 P_2 \ldots P_N
Output
Print the answer.
Sample Input 1
4 3 2 3 1 4
Sample Output 1
2
We have P = (2,3,1,4), so P_2 = 3. Thus, you should print 2.
Sample Input 2
5 2 3 5 1 4 2
Sample Output 2
5
Sample Input 3
6 6 1 2 3 4 5 6
Sample Output 3
6
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は 2 次元コード TaK Code を考案しました。以下の条件を全て満たすものが TaK Code です。
- 縦 9 マス 横 9 マスの領域である
- 左上及び右下の縦 3 マス 横 3 マスの領域に含まれる計 18 マスは全て黒である
- 左上及び右下の縦 3 マス 横 3 マスの領域に八方位で隣接する計 14 マスは全て白である
TaK Code を回転させることはできません。
縦 N マス、横 M マスのグリッドがあります。
グリッドの状態は N 個の長さ M の文字列 S_1,\ldots,S_N で与えられ、上から i 行目左から j 列目のマスは S_i の j 文字目が # のとき黒、. のとき白です。
グリッドに完全に含まれる縦 9 マス横 9 マスの領域で、TaK Code の条件を満たす箇所を全て求めてください。
制約
- 9 \leq N,M \leq 100
- N,M は整数である
- S_i は
.および#のみからなる長さ M の文字列である
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 \vdots S_N
出力
上から i 行目左から j 列目のマスを左上とする縦 9 マス 横 9 マスの領域が TaK Code の条件を満たす (i,j) の組全てを辞書順の昇順で 1 行に 1 組ずつ、i,j をこの順に空白区切りで出力せよ。
(i,j) の組の辞書順の昇順とは、i の昇順、i が等しい組は j の昇順にすることである。
入力例 1
19 18 ###......###...... ###......###...... ###..#...###..#... ..............#... .................. .................. ......###......### ......###......### ......###......### .###.............. .###......##...... .###.............. ............###... ...##.......###... ...##.......###... .......###........ .......###........ .......###........ ........#.........
出力例 1
1 1 1 10 7 7 10 2
TaK Code は以下のものです。# が黒マス、. が白マス、? が白黒どちらでもよいマスを表します。
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
入力で与えられたグリッドの上から 10 マス目左から 2 列目のマスを左上とする縦 9 マス 横 9 マスの領域は以下のようになっており、TaK Code の条件を満たします。
###...... ###...... ###...... ......... ..##..... ..##..... ......### ......### ......###
入力例 2
9 21 ###.#...........#.### ###.#...........#.### ###.#...........#.### ....#...........#.... #########...######### ....#...........#.... ....#.###...###.#.... ....#.###...###.#.... ....#.###...###.#....
出力例 2
1 1
入力例 3
18 18 ######............ ######............ ######............ ######............ ######............ ######............ .................. .................. .................. .................. .................. .................. ............###### ............###### ............###### ............###### ............###### ............######
出力例 3
TaK Code の条件を満たす箇所が 1 つもないこともあります。
Score : 200 points
Problem Statement
Takahashi invented Tak Code, a two-dimensional code. A TaK Code satisfies all of the following conditions:
- It is a region consisting of nine horizontal rows and nine vertical columns.
- All the 18 cells in the top-left and bottom-right three-by-three regions are black.
- All the 14 cells that are adjacent (horizontally, vertically, or diagonally) to the top-left or bottom-right three-by-three region are white.
It is not allowed to rotate a TaK Code.
You are given a grid with N horizontal rows and M vertical columns.
The state of the grid is described by N strings, S_1,\ldots, and S_N, each of length M. The cell at the i-th row from the top and j-th column from the left is black if the j-th character of S_i is #, and white if it is ..
Find all the nine-by-nine regions, completely contained in the grid, that satisfy the conditions of a TaK Code.
Constraints
- 9 \leq N,M \leq 100
- N and M are integers.
- S_i is a string of length M consisting of
.and#.
Input
The input is given from Standard Input in the following format:
N M S_1 \vdots S_N
Output
For all pairs (i,j) such that the nine-by-nine region, whose top-left cell is at the i-th row from the top and j-th columns from the left, satisfies the conditions of a TaK Code, print a line containing i, a space, and j in this order.
The pairs must be sorted in lexicographical ascending order; that is, i must be in ascending order, and within the same i, j must be in ascending order.
Sample Input 1
19 18 ###......###...... ###......###...... ###..#...###..#... ..............#... .................. .................. ......###......### ......###......### ......###......### .###.............. .###......##...... .###.............. ............###... ...##.......###... ...##.......###... .......###........ .......###........ .......###........ ........#.........
Sample Output 1
1 1 1 10 7 7 10 2
A TaK Code looks like the following, where # is a black cell, . is a white cell, and ? can be either black or white.
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
In the grid given by the input, the nine-by-nine region, whose top-left cell is at the 10-th row from the top and 2-nd column from the left, satisfies the conditions of a TaK Code, as shown below.
###...... ###...... ###...... ......... ..##..... ..##..... ......### ......### ......###
Sample Input 2
9 21 ###.#...........#.### ###.#...........#.### ###.#...........#.### ....#...........#.... #########...######### ....#...........#.... ....#.###...###.#.... ....#.###...###.#.... ....#.###...###.#....
Sample Output 2
1 1
Sample Input 3
18 18 ######............ ######............ ######............ ######............ ######............ ######............ .................. .................. .................. .................. .................. .................. ............###### ............###### ............###### ............###### ............###### ............######
Sample Output 3
There may be no region that satisfies the conditions of TaK Code.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
N 人の人がいます。N 人の人には人 1, 人 2,\dots, 人 N と番号がついています。
人 i(2 \le i \le N) の親は人 P_i です。ここで、P_i < i が保証されます。
人 1 が人 N の何代前か求めてください。
制約
- 2 \le N \le 50
- 1 \le P_i < i(2 \le i \le N)
- 入力は全て整数。
入力
入力は以下の形式で標準入力から与えられる。
N P_2 P_3 \dots P_N
出力
答えを整数として出力せよ。
入力例 1
3 1 2
出力例 1
2
人 2 は人 3 の親であるため、人 3 の 1 代前です。
人 1 は人 2 の親であるため、人 3 の 2 代前です。
よって解は 2 です。
入力例 2
10 1 2 3 4 5 6 7 8 9
出力例 2
9
Score : 200 points
Problem Statement
There are N people, called Person 1, Person 2, \ldots, Person N.
The parent of Person i (2 \le i \le N) is Person P_i. Here, it is guaranteed that P_i < i.
How many generations away from Person N is Person 1?
Constraints
- 2 \le N \le 50
- 1 \le P_i < i(2 \le i \le N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P_2 P_3 \dots P_N
Output
Print the answer as a positive integer.
Sample Input 1
3 1 2
Sample Output 1
2
Person 2 is a parent of Person 3, and thus is one generation away from Person 3.
Person 1 is a parent of Person 2, and thus is two generations away from Person 3.
Therefore, the answer is 2.
Sample Input 2
10 1 2 3 4 5 6 7 8 9
Sample Output 2
9
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 250 点
問題文
正整数 N が与えられます。
N 以下の正整数であって回文立方数であるものの最大値を求めてください。
ただし、正整数 K は以下の 2 つの条件を満たすとき、またそのときに限り回文立方数であると定義します。
- ある正整数 x が存在し、x^3 = K を満たす。
- K を先頭に 0 をつけずに 10 進表記した文字列が回文となる。より厳密には、0 以上 9 以下の整数 A_0, A_1, \ldots, A_{L-2} および 1 以上 9 以下の整数 A_{L-1} を用いて K = \sum_{i = 0}^{L-1} A_i10^i と表記したときに i = 0, 1, \ldots, L-1 に対して A_i = A_{L-1-i} を満たす。
制約
- N は 10^{18} 以下の正整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
345
出力例 1
343
343 は回文立方数であり、344, 345 は回文立方数ではありません。したがって、343 が答えとなります。
入力例 2
6
出力例 2
1
入力例 3
123456789012345
出力例 3
1334996994331
Score: 250 points
Problem Statement
You are given a positive integer N.
Find the maximum value of a palindromic cube number not greater than N.
Here, a positive integer K is defined to be a palindromic cube number if and only if it satisfies the following two conditions:
- There is a positive integer x such that x^3 = K.
- The decimal representation of K without leading zeros is a palindrome. More precisely, if K is represented as K = \sum_{i = 0}^{L-1} A_i10^i using integers A_0, A_1, \ldots, A_{L-2} between 0 and 9, inclusive, and an integer A_{L-1} between 1 and 9, inclusive, then A_i = A_{L-1-i} for all i = 0, 1, \ldots, L-1.
Constraints
- N is a positive integer not greater than 10^{18}.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
345
Sample Output 1
343
343 is a palindromic cube number, while 344 and 345 are not. Thus, the answer is 343.
Sample Input 2
6
Sample Output 2
1
Sample Input 3
123456789012345
Sample Output 3
1334996994331
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
正整数 N,Q と、長さ N の英小文字からなる文字列 S が与えられます。
以下で説明されるクエリを Q 個処理してください。クエリは次の 2 種類のいずれかです。
1 x: 「S の末尾の文字を削除し、先頭に挿入する」という操作を x 回連続で行う。2 x: S の x 番目の文字を出力する。
制約
- 2 \le N \le 5 \times 10^5
- 1 \le Q \le 5 \times 10^5
- 1 \le x \le N
- |S|=N
- S は英小文字からなる。
2 xの形式のクエリが 1 個以上与えられる。- N,Q,x はすべて整数。
入力
入力は以下の形式で標準入力から与えられる。
N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
それぞれのクエリは以下の形式で与えられる。ここで、t は 1 または 2 である。
t x
出力
2 x の形式の各クエリについて、答えを一行に出力せよ。
入力例 1
3 3 abc 2 2 1 1 2 2
出力例 1
b a
1 個目のクエリのとき、S は abc なので 2 文字目の b を出力します。
2 個目のクエリのとき、S は abc から cab に変わります。
3 個目のクエリのとき、S は cab なので 2 文字目の a を出力します。
入力例 2
10 8 dsuccxulnl 2 4 2 7 1 2 2 7 1 1 1 2 1 3 2 5
出力例 2
c u c u
Score : 300 points
Problem Statement
You are given positive integers N and Q, and a string S of length N consisting of lowercase English letters.
Process Q queries. Each query is of one of the following two types.
1 x: Perform the following x times in a row: delete the last character of S and append it to the beginning.2 x: Print the x-th character of S.
Constraints
- 2 \le N \le 5 \times 10^5
- 1 \le Q \le 5 \times 10^5
- 1 \le x \le N
- |S|=N
- S consists of lowercase English letters.
- At least one query in the format
2 x. - N, Q, x are all integers.
Input
Input is given from Standard Input in the following format:
N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query is in the following format, where t is 1 or 2:
t x
Output
For each query in the format 2 x, print the answer in a single line.
Sample Input 1
3 3 abc 2 2 1 1 2 2
Sample Output 1
b a
In the 1-st query, S is abc, so the 2-nd character b should be printed.
In the 2-nd query, S is changed from abc to cab.
In the 3-rd query, S is cab, so the 2-nd character a should be printed.
Sample Input 2
10 8 dsuccxulnl 2 4 2 7 1 2 2 7 1 1 1 2 1 3 2 5
Sample Output 2
c u c u
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
縦 H 行、横 W 行の H \times W マスからなるグリッドがあります。上から i 行目、左から j 列目のマスを (i, j) と表します。
各マスの状態は文字 C_{i, j} で表され、C_{i, j} = . ならばマス (i, j) は空きマスであり、C_{i, j} = # ならばマス (i, j) は壁です。
高橋君がグリッド上を歩こうとしています。彼がマス (i, j) にいるとき、マス (i, j + 1) またはマス (i + 1, j) に移動することができます。ただし、グリッドの外に出るような移動や、壁のマスへの移動を行うことはできません。高橋君は、移動することのできるマスが無くなった時点で立ち止まります。
高橋君がマス (1, 1) から歩き始めるとき、彼が立ち止まるまでに通ることのできるマスは最大で何マスですか？
制約
- 1 \leq H, W \leq 100
- H, W は整数
- C_{i, j} =
.または C_{i, j} =#(1 \leq i \leq H, 1 \leq j \leq W) - C_{1, 1} =
.
入力
入力は以下の形式で標準入力から与えられる。
H W
C_{1, 1} \ldots C_{1, W}
\vdots
C_{H, 1} \ldots C_{H, W}
出力
答えを出力せよ。
入力例 1
3 4 .#.. ..#. ..##
出力例 1
4
例えば (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) と進むことで、4 マス通ることができます。
5 マス以上通ることはできないので、4 と出力します。
入力例 2
1 1 .
出力例 2
1
入力例 3
5 5 ..... ..... ..... ..... .....
出力例 3
9
Score : 400 points
Problem Statement
There is a H \times W-square grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
Each square is described by a character C_{i, j}, where C_{i, j} = . means (i, j) is an empty square, and C_{i, j} = # means (i, j) is a wall.
Takahashi is about to start walking in this grid. When he is on (i, j), he can go to (i, j + 1) or (i + 1, j). However, he cannot exit the grid or enter a wall square. He will stop when there is no more square to go to.
When starting on (1, 1), at most how many squares can Takahashi visit before he stops?
Constraints
- 1 \leq H, W \leq 100
- H and W are integers.
- C_{i, j} =
.or C_{i, j} =#. (1 \leq i \leq H, 1 \leq j \leq W) - C_{1, 1} =
.
Input
Input is given from Standard Input in the following format:
H W
C_{1, 1} \ldots C_{1, W}
\vdots
C_{H, 1} \ldots C_{H, W}
Output
Print the answer.
Sample Input 1
3 4 .#.. ..#. ..##
Sample Output 1
4
For example, by going (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2), he can visit 4 squares.
He cannot visit 5 or more squares, so we should print 4.
Sample Input 2
1 1 .
Sample Output 2
1
Sample Input 3
5 5 ..... ..... ..... ..... .....
Sample Output 3
9
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
二次元平面上の第一象限上に N 個のフの字があります。
i\ (1 \leq i \leq N) 個目のフの字は、(x_i-1,y_i) と (x_i,y_i) を結ぶ線分と (x_i,y_i-1) と (x_i,y_i) を結ぶ線分の 2 つを組み合わせた図形です。
あなたは、N 個のフの字から 0 個以上を選び、削除することができます。
適切に削除するフの字を選んだとき、原点から全体が見えるフの字の個数は最大でいくつになりますか？
ここで、原点からあるフの字（便宜上 i 個目のフの字とする）の全体が見える必要十分条件は、以下の通りです。
- 原点、(x_i-1,y_i)、(x_i,y_i)、(x_i,y_i-1) の 4 点を頂点とする四角形の内部（境界を除く）と他のフの字が共通部分を持たない。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq x_i,y_i \leq 10^9
- (x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
x_1 y_1
x_2 y_2
\hspace{0.45cm}\vdots
x_N y_N
出力
原点から全体が見えるフの字の個数の最大値を出力せよ。
入力例 1
3 1 1 2 1 1 2
出力例 1
2
1 個目のフの字を削除したとき原点からは 2 個目のフの字と 3 個目のフの字の 2 つが見えるようになり、これが最大です。
1 つのフの字も削除しない場合、原点からは 1 個目のフの字のみしか見えません。
入力例 2
10 414598724 87552841 252911401 309688555 623249116 421714323 605059493 227199170 410455266 373748111 861647548 916369023 527772558 682124751 356101507 249887028 292258775 110762985 850583108 796044319
出力例 2
10
すべてのフの字を削除せずに残すのが最善です。
Score : 500 points
Problem Statement
There are N 7's drawn in the first quadrant of a plane.
The i-th 7 is a figure composed of a segment connecting (x_i-1,y_i) and (x_i,y_i), and a segment connecting (x_i,y_i-1) and (x_i,y_i).
You can choose zero or more from the N 7's and delete them.
What is the maximum possible number of 7's that are wholly visible from the origin after the optimal deletion?
Here, the i-th 7 is wholly visible from the origin if and only if:
- the interior (excluding borders) of the quadrilateral whose vertices are the origin, (x_i-1,y_i), (x_i,y_i), (x_i,y_i-1) does not intersect with the other 7's.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq x_i,y_i \leq 10^9
- (x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
x_1 y_1
x_2 y_2
\hspace{0.45cm}\vdots
x_N y_N
Output
Print the maximum possible number of 7's that are wholly visible from the origin.
Sample Input 1
3 1 1 2 1 1 2
Sample Output 1
2
If the first 7 is deleted, the other two 7's ― the second and third ones ― will be wholly visible from the origin, which is optimal.
If no 7's are deleted, only the first 7 is wholly visible from the origin.
Sample Input 2
10 414598724 87552841 252911401 309688555 623249116 421714323 605059493 227199170 410455266 373748111 861647548 916369023 527772558 682124751 356101507 249887028 292258775 110762985 850583108 796044319
Sample Output 2
10
It is best to keep all 7's.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
xy 平面上に高橋くんがいます。 はじめ、高橋くんは点 (s _ x,s _ y) にいます。 高橋くんは、点 (t _ x,t _ y) に移動したいです。
xy 平面上に、長方形 R\coloneqq\lbrace(x,y)\mid a-0.5\leq x\leq b+0.5,c-0.5\leq y\leq d+0.5\rbrace があります。 次の操作を考えます。
- 長方形 R に含まれる格子点 (x,y) をひとつ選ぶ。 点 (x,y) を中心に高橋くんはいまいる位置と対称な位置に瞬間移動する。
上の操作を 0 回以上 10^6 回以下繰り返して、高橋くんが点 (t _ x,t _ y) にいるようにできるか判定してください。 できる場合、高橋くんが点 (t _ x,t _ y) に移動することができるような操作の列を 1 つ構成してください。
制約
- 0\leq s _ x,s _ y,t _ x,t _ y\leq2\times10^5
- 0\leq a\leq b\leq2\times10^5
- 0\leq c\leq d\leq2\times10^5
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
s _ x s _ y t _ x t _ y a b c d
出力
1 行目には、操作を 0 回以上 10^6 回以下繰り返して高橋くんが点 (t _ x,t _ y) に到達できるなら Yes 、そうでなければ No と出力せよ。
1 行目で Yes と出力したとき、かつそのときに限り、あなたが構成した操作列の長さを d としてさらに d 行出力せよ（d は 0\leq d\leq10^6 を満たさなければならない）。
1+i 行目 (1\leq i\leq d) には、i 回目の操作で選んだ点 (x, y)\in R の座標をこの順に空白区切りで出力せよ。
入力例 1
1 2 7 8 7 9 0 3
出力例 1
Yes 7 0 9 3 7 1 8 1
例えば、次のようにして (1,2) から (7,8) へ移動することができます。
- 点 (7,0) を選ぶ。高橋くんは (13,-2) に移動する。
- 点 (9,3) を選ぶ。高橋くんは (5,8) に移動する。
- 点 (7,1) を選ぶ。高橋くんは (9,-6) に移動する。
- 点 (8,1) を選ぶ。高橋くんは (7,8) に移動する。
条件を満たす操作の列であれば何を出力しても正答となるので、例えば
Yes 7 3 9 0 7 2 9 1 8 1
と出力しても正答となります。
入力例 2
0 0 8 4 5 5 0 0
出力例 2
No
どのように操作しても点 (8,4) に移動することはできません。
入力例 3
1 4 1 4 100 200 300 400
出力例 3
Yes
高橋くんがはじめから目的地にいる場合もあります。
入力例 4
22 2 16 7 14 30 11 14
出力例 4
No
Score : 500 points
Problem Statement
Takahashi is on an xy-plane. Initially, he is at point (s _ x,s _ y), and he wants to reach point (t _ x,t _ y).
On the xy-plane is a rectangle R\coloneqq\lbrace(x,y)\mid a-0.5\leq x\leq b+0.5,c-0.5\leq y\leq d+0.5\rbrace. Consider the following operation:
- Choose a lattice point (x,y) contained in the rectangle R. Takahashi teleports to the point symmetric to his current position with respect to point (x,y).
Determine if he can reach point (t _ x,t _ y) after repeating the operation above between 0 and 10^6 times, inclusive. If it is possible, construct a sequence of operations that leads him to point (t _ x,t _ y).
Constraints
- 0\leq s _ x,s _ y,t _ x,t _ y\leq2\times10^5
- 0\leq a\leq b\leq2\times10^5
- 0\leq c\leq d\leq2\times10^5
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
s _ x s _ y t _ x t _ y a b c d
Output
In the first line, print Yes if Takahashi can reach point (t _ x,t _ y) after repeating the operation between 0 and 10^6 times, inclusive, and No otherwise.
If and only if you print Yes in the first line, print d more lines, where d is the length of the sequence of operations you have constructed (d must satisfy 0\leq d\leq10^6).
The (1+i)-th line (1\leq i\leq d) should contain the space-separated coordinates of the point (x, y)\in R, in this order, that is chosen in the i-th operation.
Sample Input 1
1 2 7 8 7 9 0 3
Sample Output 1
Yes 7 0 9 3 7 1 8 1
For example, the following choices lead him from (1,2) to (7,8).
- Choose (7,0). Takahashi moves to (13,-2).
- Choose (9,3). Takahashi moves to (5,8).
- Choose (7,1). Takahashi moves to (9,-6).
- Choose (8,1). Takahashi moves to (7,8).
Any output that satisfies the conditions is accepted; for example, printing
Yes 7 3 9 0 7 2 9 1 8 1
is also accepted.
Sample Input 2
0 0 8 4 5 5 0 0
Sample Output 2
No
No sequence of operations leads him to point (8,4).
Sample Input 3
1 4 1 4 100 200 300 400
Sample Output 3
Yes
Takahashi may already be at the destination in the beginning.
Sample Input 4
22 2 16 7 14 30 11 14
Sample Output 4
No