AtCoder Daily Training ALL 2025/11/06 20:30start

A - Strictly Increasing?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

正整数 N と、長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

A が狭義単調増加であるとは、 1\leq i\lt N なるすべての整数 i について A_i\lt A_{i+1} が成り立つことをを指します。

A が狭義単調増加であるか判定してください。

制約

2\leq N\leq 100
1\leq A_i\leq 1000 (1\leq i\leq N)
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

A が狭義単調増加であるならば Yes と、そうでないならば No と出力せよ。

正誤判定器は大文字と小文字を区別せず、どちらも受理する。例えば、答えが Yes となるときに yes や YES、yEs などと出力しても正解と判定される。

入力例 1

3
1 2 5

出力例 1

Yes

A_1\lt A_2 かつ A_2\lt A_3 なので A は狭義単調増加です。

入力例 2

3
3 9 5

出力例 2

No

A_1\lt A_2 ですが、A_2\lt A_3 でないので A は狭義単調増加ではありません。

入力例 3

10
1 1 2 3 5 8 13 21 34 55

出力例 3

No

A_1\lt A_2 でないので A は狭義単調増加ではありません。

Score : 100 points

Problem Statement

You are given a positive integer N and a sequence of positive integers A = (A_1,A_2,\dots,A_N) of length N.

Determine whether A is strictly increasing, that is, whether A_i < A_{i+1} holds for every integer i with 1 \leq i < N.

Constraints

2 \leq N \leq 100
1 \leq A_i \leq 1000 \ (1 \leq i \leq N)
All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

If A is strictly increasing, print Yes; otherwise, print No.

The judge is case-insensitive. For example, if the correct answer is Yes, any of yes, YES, and yEs will be accepted.

Sample Input 1

3
1 2 5

Sample Output 1

Yes

A_1 < A_2 and A_2 < A_3, so A is strictly increasing.

Sample Input 2

3
3 9 5

Sample Output 2

No

A_1 < A_2, but A_2 < A_3 does not hold, so A is not strictly increasing.

Sample Input 3

10
1 1 2 3 5 8 13 21 34 55

Sample Output 3

No

A_1 < A_2 does not hold, so A is not strictly increasing.

B - Rotate

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

3 つの数字 x,y,z をこの順に並べてできる 3 桁の整数を xyz と表すことにします。

どの桁も 0 でない 3 桁の整数 abc が与えられるので、abc+bca+cab を求めてください。

制約

abc はどの桁も 0 でない 3 桁の整数

入力

入力は以下の形式で標準入力から与えられる。

abc

出力

答えを出力せよ。

入力例 1

出力例 1

123+231+312=666 となります。

入力例 2

出力例 2

999+999+999=2997 となります。

Score : 100 points

Problem Statement

Let xyz denote the 3-digit integer whose digits are x, y, z from left to right.

Given a 3-digit integer abc none of whose digits is 0, find abc+bca+cab.

Constraints

abc is a 3-digit integer abc none of whose digits is 0.

Input

Input is given from Standard Input in the following format:

abc

Output

Print the answer.

Sample Input 1

Sample Output 1

We have 123+231+312=666.

Sample Input 2

Sample Output 2

We have 999+999+999=2997.

C - Failing Grade

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 人の学生が試験を受けました。学生には学生 1, 学生 2, \dots, 学生 N と番号がついていて、学生 i は a_i 点を取りました。

P 点未満の点数を取った学生は "不可" となり単位を取得できません。 "不可" となった学生の人数を答えてください。

制約

1 \leq N \leq 10^5
1 \leq P \leq 100
0 \leq a_i \leq 100 (1 \leq i \leq N)
入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N P
a_1 a_2 \dots a_N

出力

"不可" となった学生の人数を出力せよ。

入力例 1

4 50
80 60 40 0

出力例 1

学生 1 は 80 点、学生 2 は 60 点と、 50 点以上の点数を取っているので "不可" とならず単位を取得できています。
一方、学生 3 は 40 点、学生 4 は 0 点で、 50 点を下回る点数を取っているので "不可" となります。よって答えは 2 人です。

入力例 2

3 90
89 89 89

出力例 2

入力例 3

2 22
6 37

出力例 3

Score : 200 points

Problem Statement

N students took an exam. The students are labeled as Student 1, Student 2, \dots, Student N, and Student i scored a_i points.

A student who scored less than P points are considered to have failed the exam and cannot earn the credit. Find the number of students who failed the exam.

Constraints

1 \leq N \leq 10^5
1 \leq P \leq 100
0 \leq a_i \leq 100 (1 \leq i \leq N)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N P
a_1 a_2 \dots a_N

Output

Print the number of students who failed the exam.

Sample Input 1

4 50
80 60 40 0

Sample Output 1

Students 1 and 2, who scored 80 and 60 points, respectively, succeeded in scoring at least 50 points to earn the credit.
On the other hand, Students 3 and 4, who scored 40 and 0 points, respectively, fell below 50 points and failed the exam. Thus, the answer is 2.

Sample Input 2

3 90
89 89 89

Sample Output 2

Sample Input 3

2 22
6 37

Sample Output 3

D - Minimize Abs 1

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) 及び整数 L,R が与えられます。ここで L,R は L\leq R を満たします。

i=1,2,\ldots,N について以下の 2 つの条件を共に満たす整数 X_i を求めてください。なお、求める整数は常に一意に定まります。

L\leq X_i \leq R
L 以上 R 以下であるようなどの整数 Y についても |X_i - A_i| \leq |Y-A_i| を満たす

制約

1\leq N\leq 2\times 10^5
1\leq L\leq R \leq 10^9
1\leq A_i\leq 10^9
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N L R
A_1 \ldots A_N

出力

i=1,2,\ldots,N について X_i を空白区切りで出力せよ。

入力例 1

5 4 7
3 1 4 9 7

出力例 1

4 4 4 7 7

i=1 では、

|4-3|=1
|5-3|=2
|6-3|=3
|7-3|=4

より X_i = 4 です。

入力例 2

3 10 10
11 10 9

出力例 2

10 10 10

Score : 200 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and integers L and R such that L\leq R.

For each i=1,2,\ldots,N, find the integer X_i that satisfies both of the following conditions. Note that the integer to be found is always uniquely determined.

L\leq X_i \leq R.
For every integer Y such that L \leq Y \leq R, it holds that |X_i - A_i| \leq |Y - A_i|.

Constraints

1\leq N\leq 2\times 10^5
1\leq L\leq R \leq 10^9
1\leq A_i\leq 10^9
All input values are integers.

Input

The input is given from Standard Input in the following format:

N L R
A_1 \ldots A_N

Output

Print X_i for i=1,2,\ldots,N, separated by spaces.

Sample Input 1

5 4 7
3 1 4 9 7

Sample Output 1

4 4 4 7 7

For i=1:

|4-3|=1
|5-3|=2
|6-3|=3
|7-3|=4

Thus, X_i = 4.

Sample Input 2

3 10 10
11 10 9

Sample Output 2

10 10 10

E - Attraction on Rainy Day

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : {400} 点

問題文

高橋君は AtCoder Land にある屋外アトラクションに K 回乗ろうとしています。このアトラクションの一回の所要時間は T です。

現在の時刻は 0 です。時刻 0 から N までの降水量が与えられます。時刻 i から時刻 i+1 までの降水量は P_i です (0\leq i\lt N)。アトラクションには時刻 0,1,…,N−T に乗ることができます。時刻 t にアトラクションに乗ると時刻 t+T にアトラクションから降りることができ、アトラクションに乗っている間に P_t+P_{t+1}+\dots+P_{t+T-1} だけ濡れます。

高橋君はアトラクションに乗っている間にできるだけ雨に濡れないようにしたいです。時刻 N までに K 回アトラクションに乗るとき、高橋君が濡れる量の総和の最小値を求めてください。ただし、乗り換えにかかる時間や待ち時間は 0 とし、アトラクションから降りた時刻に新たにアトラクションに乗ることができるものとします。

制約

1\leq N\leq 2\times 10^5
1\leq K\leq \min(N,100)
1\leq T\leq N/K
0\leq P_i\leq 10^{9}
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N K T
P_0 P_1 \ldots P_{N-1}

出力

答えを出力せよ。

入力例 1

8 3 2
3 5 10 4 1 7 3 9

出力例 1

次のようにアトラクションに 3 回乗ることで濡れる量を合計で 23 にすることができ、これが最小です。

アトラクションに時刻 0 に乗り、時刻 2 に降りる。この間に P_0+P_1=3+5=8 濡れる。
アトラクションに時刻 3 に乗り、時刻 5 に降りる。この間に P_3+P_4=4+1=5 濡れる。
アトラクションに時刻 5 に乗り、時刻 7 に降りる。この間に P_5+P_6=7+3=10 濡れる。

入力例 2

5 1 3
1000 1 10000 100 10

出力例 2

入力例 3

15 5 2
401054171 63773035 986525245 157986893 799814573 139201145 649233932 351289844 409065258 406122133 957285954 529460482 21179081 795984182 727882733

出力例 3

3522058414

F - Coupon

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 個の商品があります。i = 1, 2, \ldots, N について、i 番目の商品の値段は A_i 円です。

高橋君は K 枚のクーポンを持っています。
1 枚のクーポンは 1 つの商品に対して使用することができ、1 つの商品に対してはクーポンを何枚でも（ 0 枚でもよい）使用することができます。値段が a 円の商品に対して k 枚のクーポンを使用すると、その商品を \max\lbrace a - kX, 0\rbrace 円で買うことができます。

高橋君がすべての商品を買うために支払う合計金額の最小値を出力してください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq K, X \leq 10^9
1 \leq A_i \leq 10^9
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K X
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

5 4 7
8 3 10 5 13

出力例 1

1 番目の商品に対してクーポン 1 枚、3 番目の商品に対してクーポン 1 枚、5 番目の商品に対してクーポン 2 枚を使用すると、

1 番目の商品を \max\lbrace A_1-X, 0 \rbrace = 1 円で買うことができ、
2 番目の商品を \max\lbrace A_2, 0 \rbrace = 3 円で買うことができ、
3 番目の商品を \max\lbrace A_3-X, 0 \rbrace = 3 円で買うことができ、
4 番目の商品を \max\lbrace A_4, 0 \rbrace = 5 円で買うことができ、
5 番目の商品を \max\lbrace A_5-2X, 0 \rbrace = 0 円で買うことができます。

よって、すべての商品を 1 + 3 + 3 + 5 + 0 = 12 円で買うことができ、これが最小です。

入力例 2

5 100 7
8 3 10 5 13

出力例 2

入力例 3

20 815 60
2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202

出力例 3

Score : 300 points

Problem Statement

There are N items in a shop. For each i = 1, 2, \ldots, N, the price of the i-th item is A_i yen (the currency of Japan).

Takahashi has K coupons.
Each coupon can be used on one item. You can use any number of coupons, possibly zero, on the same item. Using k coupons on an item with a price of a yen allows you to buy it for \max\lbrace a - kX, 0\rbrace yen.

Print the minimum amount of money Takahashi needs to buy all the items.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq K, X \leq 10^9
1 \leq A_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K X
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

5 4 7
8 3 10 5 13

Sample Output 1

By using 1 coupon on the 1-st item, 1 coupon on the 3-rd item, and 2 coupons on the 5-th item, Takahashi can:

buy the 1-st item for \max\lbrace A_1-X, 0 \rbrace = 1 yen,
buy the 2-nd item for \max\lbrace A_2, 0 \rbrace = 3 yen,
buy the 3-rd item for \max\lbrace A_3-X, 0 \rbrace = 3 yen,
buy the 4-th item for \max\lbrace A_4, 0 \rbrace = 5 yen,
buy the 5-th item for \max\lbrace A_5-2X, 0 \rbrace = 0 yen,

for a total of 1 + 3 + 3 + 5 + 0 = 12 yen, which is the minimum possible.

Sample Input 2

5 100 7
8 3 10 5 13

Sample Output 2

Sample Input 3

20 815 60
2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202

Sample Output 3

G - Transmission Mission

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

数直線上に N 棟の家があり、1 から N までの番号が付けられています。家 i は座標 X_i に位置しています。同じ座標に複数の家が位置していることもあります。

あなたは M 個の基地局を数直線上の任意の実数座標に配置します。そして、それぞれの基地局に対して非負整数の値の電波強度を設定します。

ある基地局の電波強度を x にしたとき、その基地局からの電波が家に届く条件は、その基地局とその家の距離が \displaystyle\frac{x}{2} 以下であることです。特に x=0 の場合、その基地局と同じ座標に位置する家にのみ電波が届きます。

どの家にも少なくとも 1 つの基地局から電波が届くように基地局の位置と電波強度を設定するとき、電波強度の総和がとりうる最小値を求めてください。

なお、制約を満たす任意の入力に対して答えが整数であることが証明できます。

制約

1 \leq M \leq N \leq 5 \times 10^5
1 \leq X_i \leq 10^{12} (1 \leq i \leq N)
入力される数値は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N M
X_1 \dots X_N

出力

答えを整数として 1 行で出力せよ。

入力例 1

7 3
5 10 15 20 8 14 15

出力例 1

以下のように 3 つの基地局を置くことで、すべての家に電波が届きます。

座標 7.5 に電波強度 5 の基地局を置く。この基地局から電波が届くのは家 1,2,5 である。
座標 14.5 に電波強度 1 の基地局を置く。この基地局から電波が届くのは家 3,6,7 である。
座標 20 に電波強度 0 の基地局を置く。この基地局から電波が届くのは家 4 である。

このときの電波強度の総和は 6 です。

電波強度の総和が 6 より小さい配置で条件を達成することはできないので、6 を出力します。

入力例 2

7 7
5 10 15 20 8 14 15

出力例 2

入力例 3

7 1
5 10 15 20 8 14 15

出力例 3

Score : 400 points

Problem Statement

There are N houses numbered from 1 to N on a number line. House i is located at coordinate X_i. Multiple houses may be located at the same coordinate.

You place M base stations at arbitrary real coordinates on the number line. Then, you set a non-negative integer signal strength for each base station.

When the signal strength of a base station is set to x, The signal from that base station reaches a house if and only if the distance between the base station and the house is at most \displaystyle\frac{x}{2}. Particularly, when x=0, the signal reaches only houses located at the same coordinate as the base station.

Find the minimum possible sum of signal strengths when the positions and signal strengths of the base stations are set such that at least one base station's signal reaches every house.

It can be proved that the answer is an integer for any input satisfying the constraints.

Constraints

1 \leq M \leq N \leq 5 \times 10^5
1 \leq X_i \leq 10^{12} (1 \leq i \leq N)
All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
X_1 \dots X_N

Output

Output the answer as an integer in one line.

Sample Input 1

7 3
5 10 15 20 8 14 15

Sample Output 1

By placing three base stations as follows, signals reach all houses.

Place a base station with signal strength 5 at coordinate 7.5. This base station reaches houses 1,2,5.
Place a base station with signal strength 1 at coordinate 14.5. This base station reaches houses 3,6,7.
Place a base station with signal strength 0 at coordinate 20. This base station reaches house 4.

The sum of signal strengths in this case is 6.

It is impossible to satisfy the condition with an arrangement where the sum of signal strengths is smaller than 6, so output 6.

Sample Input 2

7 7
5 10 15 20 8 14 15

Sample Output 2

Sample Input 3

7 1
5 10 15 20 8 14 15

Sample Output 3

H - Reachability Query

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

N 頂点 0 辺の無向グラフが与えられます。
頂点には 1,2,\dots,N の番号が付けられており、最初は全ての頂点が白色です。
以下の 3 種類のクエリを合計 Q 個処理して下さい。

タイプ 1 : 頂点 u,v を結ぶ無向辺を追加する。
タイプ 2 : 頂点 v が白色なら黒色に、黒色なら白色に変更する。
タイプ 3 : 頂点 v から 0 本以上の辺を辿って黒色の頂点に到達できるか判定し、到達できるなら Yes 、到達できないなら No と答える。

制約

入力は全て整数
1 \le N \le 2 \times 10^5
1 \le Q \le 6 \times 10^5
タイプ 1 のクエリは以下の制約を満たす。
- 1 \le u < v \le N
- 各クエリについて、そのクエリより前に u,v を結ぶ辺は追加されていない。
タイプ 2,3 のクエリは以下の制約を満たす。
- 1 \le v \le N

入力

入力は以下の形式で標準入力から与えられる。

N Q
\rm{Query}_1
\rm{Query}_2
\vdots
\rm{Query}_Q

但し、 \rm{Query}_i は i 個目のクエリを表す。

タイプ 1 のクエリは以下の形式で与えられる。

1 u v

タイプ 2 のクエリは以下の形式で与えられる。

2 v

タイプ 3 のクエリは以下の形式で与えられる。

3 v

出力

タイプ 3 のクエリが現れる度に、その解答を次の通りに出力せよ。

頂点 v から 0 本以上の辺を辿って黒色の頂点に到達できるなら Yes
頂点 v から 0 本以上の辺を辿って黒色の頂点に到達できないなら No

入力例 1

出力例 1

No
Yes
No
Yes
Yes
No

この入力では、グラフは最初 5 頂点 0 辺です。
この入力には 12 個のクエリが含まれます。

1 個目のクエリは 3 2 です。
- この時点で頂点 2 から 0 本以上の辺を辿って黒色の頂点に到達できないので、 No と解答します。
2 個目のクエリは 2 2 です。
- 頂点 2 は白色なので、黒色に変更します。
3 個目のクエリは 3 2 です。
- この時点で頂点 2 から 0 本以上の辺を辿って黒色の頂点 2 に到達できます。よって、 Yes と解答します。
4 個目のクエリは 1 2 5 です。
- 頂点 2,5 を結ぶ辺を追加します。
5 個目のクエリは 1 3 4 です。
- 頂点 3,4 を結ぶ辺を追加します。
6 個目のクエリは 3 4 です。
- この時点で頂点 4 から 0 本以上の辺を辿って黒色の頂点に到達できないので、 No と解答します。
7 個目のクエリは 3 5 です。
- この時点で頂点 5 から 0 本以上の辺を辿って黒色の頂点 2 に到達できます。よって、 Yes と解答します。
8 個目のクエリは 1 4 5 です。
- 頂点 4,5 を結ぶ辺を追加します。
9 個目のクエリは 1 1 3 です。
- 頂点 1,3 を結ぶ辺を追加します。
10 個目のクエリは 3 1 です。
- この時点で頂点 1 から 0 本以上の辺を辿って黒色の頂点 2 に到達できます。よって、 Yes と解答します。
11 個目のクエリは 2 2 です。
- 頂点 2 は黒色なので、白色に変更します。
12 個目のクエリは 3 1 です。
- この時点で頂点 1 から 0 本以上の辺を辿って黒色の頂点に到達できないので、 No と解答します。

Score : 450 points

Problem Statement

You are given an undirected graph with N vertices and zero edges.
The vertices are numbered 1,2,\dots,N, and initially all vertices are white.
Process a total of Q queries of the following three types:

Type 1 : Add an undirected edge connecting vertices u and v.
Type 2 : If vertex v is white, change it to black; if it is black, change it to white.
Type 3 : Determine whether a black vertex can be reached from vertex v by traversing zero or more edges; report Yes if reachable, and No otherwise.

Constraints

All input values are integers.
1 \le N \le 2 \times 10^5
1 \le Q \le 6 \times 10^5
Type 1 queries satisfy the following constraints:
- 1 \le u < v \le N
- For each query, no edge connecting u and v has been added before that query.
Type 2,3 queries satisfy the following constraints:
- 1 \le v \le N

Input

The input is given from Standard Input in the following format:

N Q
\rm{Query}_1
\rm{Query}_2
\vdots
\rm{Query}_Q

where \rm{Query}_i represents the i-th query.

Type 1 queries are given in the following format:

1 u v

Type 2 queries are given in the following format:

2 v

Type 3 queries are given in the following format:

3 v

Output

For each type 3 query, output the answer as follows:

Yes if a black vertex can be reached from vertex v by traversing zero or more edges;
No if no black vertex can be reached from vertex v by traversing zero or more edges.

Sample Input 1

Sample Output 1

No
Yes
No
Yes
Yes
No

In this input, the graph initially has five vertices and zero edges.
This input contains 12 queries.

The 1st query is 3 2.
- At this point, no black vertex can be reached from vertex 2 by traversing zero or more edges, so report No.
The 2nd query is 2 2.
- Vertex 2 is white, so change it to black.
The 3rd query is 3 2.
- At this point, black vertex 2 can be reached from vertex 2 by traversing zero or more edges. Therefore, report Yes.
The 4th query is 1 2 5.
- Add an edge connecting vertices 2,5.
The 5th query is 1 3 4.
- Add an edge connecting vertices 3,4.
The 6th query is 3 4.
- At this point, no black vertex can be reached from vertex 4 by traversing zero or more edges, so report No.
The 7th query is 3 5.
- At this point, black vertex 2 can be reached from vertex 5 by traversing zero or more edges. Therefore, report Yes.
The 8th query is 1 4 5.
- Add an edge connecting vertices 4,5.
The 9th query is 1 1 3.
- Add an edge connecting vertices 1,3.
The 10th query is 3 1.
- At this point, black vertex 2 can be reached from vertex 1 by traversing zero or more edges. Therefore, report Yes.
The 11th query is 2 2.
- Vertex 2 is black, so change it to white.
The 12th query is 3 1.
- At this point, no black vertex can be reached from vertex 1 by traversing zero or more edges, so report No.

I - Teleporter Takahashi

Time Limit: 2 sec / Memory Limit: 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

例えば、次のようにして (1,2) から (7,8) へ移動することができます。

点 (7,0) を選ぶ。高橋くんは (13,-2) に移動する。
点 (9,3) を選ぶ。高橋くんは (5,8) に移動する。
点 (7,1) を選ぶ。高橋くんは (9,-6) に移動する。
点 (8,1) を選ぶ。高橋くんは (7,8) に移動する。

条件を満たす操作の列であれば何を出力しても正答となるので、例えば

と出力しても正答となります。

入力例 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

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

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