A - Grapes

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

1 から N までの番号がついた N 人の人がいます。

M 粒のぶどうがあります。これらを次のようにして N 人に配ります。

  • 人 1,2,\dots,N の順に 1 粒ずつ配る。途中でぶどうがなくなったらその時点で終了する。
  • 人 N に配った後もまだぶどうが残っている場合は、人 1 に戻って再び順番に配る。これをぶどうがなくなるまで繰り返す。

各人が何粒のぶどうをもらうかを求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq M \leq 10000
  • 入力はすべて整数

入力

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

N M

出力

N 行出力せよ。 i 行目には人 i がもらうぶどうの粒数を出力せよ。


入力例 1

3 5

出力例 1

2
2
1

5 粒のぶどうを人 1,2,3,1,2 の順に 1 粒ずつ配ります。


入力例 2

4 1

出力例 2

1
0
0
0

1 粒ももらえない人がいる可能性もあります。


入力例 3

12 3456

出力例 3

288
288
288
288
288
288
288
288
288
288
288
288

全員が同じ粒数もらう可能性もあります。

Score : 100 points

Problem Statement

There are N people numbered from 1 to N.

There are M grapes. They will be distributed to the N people as follows.

  • Give one grape each to persons 1,2,\dots,N in this order. If the grapes run out midway, the distribution ends at that point.
  • If there are still grapes remaining after giving to person N, go back to person 1 and distribute in order again. Repeat this until the grapes run out.

Find how many grapes each person receives.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq M \leq 10000
  • All input values are integers.

Input

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

N M

Output

Output N lines. The i-th line should contain the number of grapes person i receives.


Sample Input 1

3 5

Sample Output 1

2
2
1

The five grapes are given one at a time to persons 1,2,3,1,2 in this order.


Sample Input 2

4 1

Sample Output 2

1
0
0
0

There may be people who receive no grape.


Sample Input 3

12 3456

Sample Output 3

288
288
288
288
288
288
288
288
288
288
288
288

Everyone may receive the same number of grapes.

B - Topping

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

高橋君はラーメン屋に来ています。

このラーメン屋では N 種類のトッピングがあり、i 番目のトッピングは価格が i、嬉しさが W_i です。

高橋君は、価格の総和が V 以下になるように相異なる 3 種類のトッピングを選びます。 高橋君が選んだトッピングの嬉しさの総和の最大値を求めてください。

ただし、価格の総和が V 以下になるように相異なる 3 種類のトッピングを選ぶ方法が 1 通り以上存在することが制約より保証されます。

制約

  • 3 \leq N \leq 100
  • 6 \leq V \leq 3N-3
  • 1 \leq W_i \leq 10^6
  • 入力はすべて整数

入力

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

N V
W_1 W_2 \dots W_N

出力

答えを一行で出力せよ。


入力例 1

5 9
31 41 59 26 53

出力例 1

143

1,3,5 番目のトッピングを選んだとき、価格の総和は 1+3+5=9、嬉しさの総和は 31+59+53=143 です。


入力例 2

10 16
102228 448944 131224 326172 500169 670309 976672 579051 974511 773940

出力例 2

2095925

2,6,7 番目のトッピングを選んだとき、価格の総和は 2+6+7=15、嬉しさの総和は 448944+670309+976672=2095925 です。

Score : 200 points

Problem Statement

Takahashi is at a ramen shop.

This shop has N kinds of toppings, and the i-th topping has a price of i and a happiness of W_i.

Takahashi chooses three distinct kinds of toppings so that the total price is at most V. Find the maximum possible total happiness of the toppings he chooses.

The constraints guarantee that there is at least one way to choose three distinct kinds of toppings so that the total price is at most V.

Constraints

  • 3 \leq N \leq 100
  • 6 \leq V \leq 3N-3
  • 1 \leq W_i \leq 10^6
  • All input values are integers.

Input

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

N V
W_1 W_2 \dots W_N

Output

Output the answer in one line.


Sample Input 1

5 9
31 41 59 26 53

Sample Output 1

143

When choosing the first, third, and fifth toppings, the total price is 1+3+5=9, and the total happiness is 31+59+53=143.


Sample Input 2

10 16
102228 448944 131224 326172 500169 670309 976672 579051 974511 773940

Sample Output 2

2095925

When choosing the second, sixth, and seventh toppings, the total price is 2+6+7=15, and the total happiness is 448944+670309+976672=2095925.

C - Sort Subarray

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

長さ N の整数列 A=(A _ 1,A _ 2,\ldots,A _ N) が与えられます。

A に対して、次の操作をちょうど \mathbf{1} 回行います。

  • 1 以上 N-K+1 以下の整数 i をひとつ選ぶ。A _ i,A _ {i+1},\ldots,A _ {i+K-1} を昇順にソートする。より厳密には、A _ i,A _ {i+1},\ldots,A _ {i+K-1} を小さいほうから順に並べたものを B _ 1,B _ 2,\ldots,B _ K とし、1\le j\le K について一斉に A _ {i+j-1} を B _ j で置き換える。

この操作ののち、A が昇順になっている、つまりすべての 1\le i\lt N に対して A _ i\le A _ {i+1} が成り立っているようにできるか判定してください。

制約

  • 1\le K\lt N\le2\times10 ^ 5
  • 1\le A _ i\le N\ (1\le i\le N)
  • 入力は全て整数

入力

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

N K
A _ 1 A _ 2 \ldots A _ N

出力

操作を 1 回行うことで A を昇順に並べ替えられるなら Yes を、そうでなければ No を出力せよ。


入力例 1

9 6
1 4 1 4 2 1 3 5 6

出力例 1

Yes

例えば、i として 2 を選ぶと、(A _ 2,A _ 3,A _ 4,A _ 5,A _ 6,A _ 7)=(4,1,4,2,1,3) が (1,1,2,3,4,4) に置き換えられます。 操作が終わったあとの A は (1,1,1,2,3,4,4,5,6) となり、条件を満たします。

よって、Yes を出力してください。


入力例 2

3 1
3 2 1

出力例 2

No

K=1 なので、どの i に対して操作を行っても A は変化しません。 よって、No を出力してください。


入力例 3

30 25
1 2 2 22 14 10 14 10 18 5 15 8 17 22 10 17 11 25 13 16 9 19 26 7 11 12 23 3 30 30

出力例 3

Yes

Score : 300 points

Problem Statement

You are given a length-N integer sequence A=(A _ 1,A _ 2,\ldots,A _ N).

You will perform the following operation on A exactly once.

  • Choose an integer i between 1 and N-K+1, inclusive. Sort A _ i,A _ {i+1},\ldots,A _ {i+K-1} in ascending order. More formally, let B _ 1,B _ 2,\ldots,B _ K be A _ i,A _ {i+1},\ldots,A _ {i+K-1} arranged in increasing order, and simultaneously replace A _ {i+j-1} with B _ j for 1\le j\le K.

Determine whether it is possible that, after this operation, A is in ascending order, that is, A _ i\le A _ {i+1} holds for all 1\le i\lt N.

Constraints

  • 1\le K\lt N\le2\times10 ^ 5
  • 1\le A _ i\le N\ (1\le i\le N)
  • All input values are integers.

Input

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

N K
A _ 1 A _ 2 \ldots A _ N

Output

If A can be sorted in ascending order by performing the operation once, output Yes; otherwise, output No.


Sample Input 1

9 6
1 4 1 4 2 1 3 5 6

Sample Output 1

Yes

For example, if you choose 2 as i, then (A _ 2,A _ 3,A _ 4,A _ 5,A _ 6,A _ 7)=(4,1,4,2,1,3) is replaced with (1,1,2,3,4,4). After the operation, A is (1,1,1,2,3,4,4,5,6), which satisfies the condition.

Thus, output Yes.


Sample Input 2

3 1
3 2 1

Sample Output 2

No

K=1, so A does not change regardless of which i the operation is performed on. Thus, output No.


Sample Input 3

30 25
1 2 2 22 14 10 14 10 18 5 15 8 17 22 10 17 11 25 13 16 9 19 26 7 11 12 23 3 30 30

Sample Output 3

Yes
D - Range Set Insertion Query

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

N 個の集合 S _ 1,S _ 2,\ldots,S _ N があります。 はじめ、S _ 1,S _ 2,\ldots,S _ N はすべて空集合です。

これらの集合に対して、以下のような操作を Q 回行います。i 番目 (1\le i\le Q) の操作では、整数の 3 つ組 (L _ i,R _ i,X _ i) が与えられ、以下の操作を行います。

  • S _ {L _ i},S _ {L _ i+1},\ldots,S _ {R _ i} に対して、X _ i を追加する。

すべての操作を終えたあとの S _ i の要素数を、すべての i=1,2,\ldots,N に対して求めてください。

制約

  • 1\le N\le2\times10 ^ 5
  • 1\le Q\le2\times10 ^ 5
  • 1\le L _ i\le R _ i\le N\ (1\le i\le Q)
  • 1\le X _ i\le Q\ (1\le i\le Q)
  • 入力はすべて整数

入力

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

N Q
L _ 1 R _ 1 X _ 1
L _ 2 R _ 2 X _ 2
\vdots
L _ Q R _ Q X _ Q

出力

Q 回の操作をすべて終えたあとの、S _ 1 の要素数,S _ 2 の要素数,\ldots,S _ N の要素数をこの順に空白を区切りとして出力せよ。


入力例 1

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

出力例 1

1 2 3 3 3 1 1 1

5 回の操作ののち、それぞれの集合は \lbrace2\rbrace,\lbrace1,2\rbrace,\lbrace1,2,3\rbrace,\lbrace1,2,3\rbrace,\lbrace1,2,3\rbrace,\lbrace3\rbrace,\lbrace1\rbrace,\lbrace1\rbrace となります。 よって、それぞれの集合の要素数である 1,2,3,3,3,1,1,1 を、この順に空白を区切りとして出力してください。


入力例 2

30 20
3 22 11
8 30 10
12 14 7
2 17 4
1 19 12
7 30 15
11 23 2
14 25 17
9 12 7
10 16 7
16 18 19
1 11 14
11 15 4
1 21 6
4 8 10
23 24 11
8 27 10
1 19 12
23 23 16
13 24 12

出力例 2

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

Score : 400 points

Problem Statement

There are N sets S _ 1,S _ 2,\ldots,S _ N. Initially, S _ 1,S _ 2,\ldots,S _ N are all empty sets.

The following operation is performed Q times on these sets. In the i-th operation (1\le i\le Q), a triple of integers (L _ i,R _ i,X _ i) is given, and the operation below is performed.

  • Add X _ i to S _ {L _ i},S _ {L _ i+1},\ldots,S _ {R _ i}.

For every i=1,2,\ldots,N, find the number of elements of S _ i after all operations are finished.

Constraints

  • 1\le N\le2\times10 ^ 5
  • 1\le Q\le2\times10 ^ 5
  • 1\le L _ i\le R _ i\le N\ (1\le i\le Q)
  • 1\le X _ i\le Q\ (1\le i\le Q)
  • All input values are integers.

Input

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

N Q
L _ 1 R _ 1 X _ 1
L _ 2 R _ 2 X _ 2
\vdots
L _ Q R _ Q X _ Q

Output

Output the number of elements of S _ 1, the number of elements of S _ 2,\ldots, the number of elements of S _ N after all Q operations are finished, in this order, separated by spaces.


Sample Input 1

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

Sample Output 1

1 2 3 3 3 1 1 1

After the five operations, the sets are \lbrace2\rbrace,\lbrace1,2\rbrace,\lbrace1,2,3\rbrace,\lbrace1,2,3\rbrace,\lbrace1,2,3\rbrace,\lbrace3\rbrace,\lbrace1\rbrace,\lbrace1\rbrace, respectively. Thus, output their numbers of elements, 1,2,3,3,3,1,1,1, in this order, separated by spaces.


Sample Input 2

30 20
3 22 11
8 30 10
12 14 7
2 17 4
1 19 12
7 30 15
11 23 2
14 25 17
9 12 7
10 16 7
16 18 19
1 11 14
11 15 4
1 21 6
4 8 10
23 24 11
8 27 10
1 19 12
23 23 16
13 24 12

Sample Output 2

3 4 5 6 6 6 7 7 8 8 9 8 8 9 9 10 9 8 7 7 7 6 7 5 3 2 2 2 2 2
E - lt and le

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 475 点

問題文

1 以上 N 以下の整数からなる長さ N の整数列 A であって、次の Q 個の条件をすべて満たすものが存在するか判定し、存在する場合 1 つ求めてください。

i 番目 (1\le i\le Q) の条件は整数の 3 つ組 (t _ i,u _ i,v _ i) で与えられ、以下のように定義されます。

  • t _ i=0 のとき、A _ {u _ i}\le A _ {v _ i}
  • t _ i=1 のとき、A _ {u _ i}\lt A _ {v _ i}

すべての条件を満たす列が複数存在するときは、どれを出力しても構いません。

制約

  • 1\le N\le2\times10 ^ 5
  • 1\le Q\le2\times10 ^ 5
  • t _ i\in\lbrace0,1\rbrace\ (1\le i\le Q)
  • 1\le u _ i\le N\ (1\le i\le Q)
  • 1\le v _ i\le N\ (1\le i\le Q)
  • 入力はすべて整数

入力

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

N Q
t _ 1 u _ 1 v _ 1
t _ 2 u _ 2 v _ 2
\vdots
t _ Q u _ Q v _ Q

出力

1 行目には、条件を満たす整数列が存在すれば Yes 、そうでなければ No を出力せよ。 1 行目に Yes を出力したとき、2 行目には条件を満たす整数列を 1 つ選び、その要素を空白を区切りとして出力せよ。 すべての条件を満たす列が複数存在するときは、どれを選んでも構わない。


入力例 1

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

出力例 1

Yes
1 4 2 1 3 5 6

A=(1,4,2,1,3,5,6) とすると、これは 1 以上 7 以下の整数からなる長さ 7 の整数列です。 ここで、例えば 1 番目の条件 A _ 1\le A _ 4 は 1\le 1 なので成り立っています。 他の 7 個の条件も成り立つため、A=(1,4,2,1,3,5,6) に対応する出力は正答とみなされます。

他にも、A=(1,1,1,1,2,2,3) や A=(3,5,4,3,6,7,7) なども条件を満たすため、これらを出力しても正答とみなされます。


入力例 2

1 1
1 1 1

出力例 2

No

A _ 1\lt A _ 1 が成り立つような整数列 A は存在しません。


入力例 3

15 20
0 9 8
1 6 1
0 6 8
0 11 1
0 4 2
1 11 12
0 4 14
1 10 1
0 12 12
1 7 12
1 13 1
1 5 9
1 10 14
1 14 1
1 8 12
0 10 12
1 4 15
1 3 9
0 5 14
0 10 2

出力例 3

Yes
15 14 10 7 6 5 4 12 11 3 2 13 1 9 8

Score : 475 points

Problem Statement

Determine whether there exists an integer sequence A of length N consisting of integers between 1 and N, inclusive, that satisfies all of the following Q conditions, and if it exists, find one.

The i-th condition (1\le i\le Q) is given by a triple of integers (t _ i,u _ i,v _ i), and is defined as follows.

  • If t _ i=0: A _ {u _ i}\le A _ {v _ i}
  • If t _ i=1: A _ {u _ i}\lt A _ {v _ i}

If there are multiple sequences satisfying all conditions, you may output any of them.

Constraints

  • 1\le N\le2\times10 ^ 5
  • 1\le Q\le2\times10 ^ 5
  • t _ i\in\lbrace0,1\rbrace\ (1\le i\le Q)
  • 1\le u _ i\le N\ (1\le i\le Q)
  • 1\le v _ i\le N\ (1\le i\le Q)
  • All input values are integers.

Input

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

N Q
t _ 1 u _ 1 v _ 1
t _ 2 u _ 2 v _ 2
\vdots
t _ Q u _ Q v _ Q

Output

On the first line, output Yes if an integer sequence satisfying the conditions exists, and No otherwise. If you output Yes on the first line, choose one integer sequence satisfying the conditions and output its elements, separated by spaces, on the second line. If there are multiple sequences satisfying all conditions, you may choose any of them.


Sample Input 1

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

Sample Output 1

Yes
1 4 2 1 3 5 6

Let A=(1,4,2,1,3,5,6); this is an integer sequence of length 7 consisting of integers between 1 and 7, inclusive. Here, for example, the first condition A _ 1\le A _ 4 holds since 1\le 1. The other seven conditions also hold, so the output corresponding to A=(1,4,2,1,3,5,6) is considered correct.

Additionally, A=(1,1,1,1,2,2,3), A=(3,5,4,3,6,7,7), and others also satisfy the conditions, so outputting these is also considered correct.


Sample Input 2

1 1
1 1 1

Sample Output 2

No

There is no integer sequence A such that A _ 1\lt A _ 1 holds.


Sample Input 3

15 20
0 9 8
1 6 1
0 6 8
0 11 1
0 4 2
1 11 12
0 4 14
1 10 1
0 12 12
1 7 12
1 13 1
1 5 9
1 10 14
1 14 1
1 8 12
0 10 12
1 4 15
1 3 9
0 5 14
0 10 2

Sample Output 3

Yes
15 14 10 7 6 5 4 12 11 3 2 13 1 9 8
F - Min-First Search

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 525 点

問題文

頂点 1, 頂点 2,\ldots, 頂点 N からなる N 頂点の木 T に対して、以下の手順で得られる (1,2,\ldots,N) の順列 P を f(T) とします。

  • はじめ、列 P を空列 () とし、集合 S を \lbrace1\rbrace とする。
  • 以下を N 回繰り返す。
    • S の最小値を x とする。S から x を削除し、P の末尾に xを追加する。
    • その後、T において頂点 x に隣接する頂点を頂点 v _ 1, 頂点 v _ 2,\ldots, 頂点 v _ k とする。i=1,2,\ldots,k について、P に v _ i が含まれていなければ S に v _ i を追加する。

(1,2,\ldots,N) の順列 Q=(Q _ 1,Q _ 2,\ldots,Q _ N) が与えられます。 f(T)=Q となる木 T の個数を 998244353 で割った余りを求めてください。 ただし、ふたつの木は、ある頂点の組 (u,v) が存在して、一方の木では頂点 u と頂点 v の間に辺があり、もう一方の木では辺がないとき、区別されます。

制約

  • 1\le N\le2\times10 ^ 5
  • 1\le Q _ i\le N\ (1\le i\le N)
  • Q _ i\ne Q _ j\ (1\le i\lt j\le N)
  • Q _ 1=1
  • 入力はすべて整数

入力

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

N
Q _ 1 Q _ 2 \ldots Q _ N

出力

f(T)=Q となる木 T の個数を 998244353 で割った余りを出力せよ。


入力例 1

5
1 3 4 2 5

出力例 1

8

例えば、以下のような木を T とすると、f(T)=Q となります。

f(T) を求める手順は以下の図のように進行します。

この木を含めた以下の図のような 8 つの木が条件を満たします。

よって、8 を出力してください。


入力例 2

20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

出力例 2

868586527

条件を満たす木の個数を 998244353 で割った余りを出力してください。


入力例 3

30
1 16 23 14 18 10 12 21 27 30 17 28 4 9 20 13 22 11 19 3 25 26 6 7 2 8 5 24 15 29

出力例 3

910753763

Score : 525 points

Problem Statement

For a tree T with N vertices called vertex 1, vertex 2, \ldots, vertex N, let f(T) be the permutation P of (1,2,\ldots,N) obtained by the following procedure.

  • Initially, let the sequence P be the empty sequence (), and let the set S be \lbrace1\rbrace.
  • Repeat the following N times.
    • Let x be the minimum value of S. Remove x from S, and append x to the end of P.
    • Then, let v_1, v_2, \ldots, v_k be the vertices adjacent to vertex x in T. For i=1,2,\ldots,k, if v _ i is not contained in P, add v _ i to S.

You are given a permutation Q=(Q _ 1,Q _ 2,\ldots,Q _ N) of (1,2,\ldots,N). Find the number, modulo 998244353, of trees T such that f(T)=Q. Here, two trees are distinguished when there exists a pair of vertices (u,v) such that there is an edge between vertex u and vertex v in one tree and there is no edge in the other tree.

Constraints

  • 1\le N\le2\times10 ^ 5
  • 1\le Q _ i\le N\ (1\le i\le N)
  • Q _ i\ne Q _ j\ (1\le i\lt j\le N)
  • Q _ 1=1
  • All input values are integers.

Input

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

N
Q _ 1 Q _ 2 \ldots Q _ N

Output

Output the number, modulo 998244353, of trees T such that f(T)=Q.


Sample Input 1

5
1 3 4 2 5

Sample Output 1

8

For example, if T is the following tree, then f(T)=Q.

The procedure to find f(T) proceeds as shown in the following figure.

Including this tree, the following eight trees satisfy the condition.

Thus, output 8.


Sample Input 2

20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Sample Output 2

868586527

Output modulo 998244353 the number of trees satisfying the condition.


Sample Input 3

30
1 16 23 14 18 10 12 21 27 30 17 28 4 9 20 13 22 11 19 3 25 26 6 7 2 8 5 24 15 29

Sample Output 3

910753763
G - Division Point Hull

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 625 点

問題文

座標平面上に N 個の点 P_1,P_2,\dots,P_N があります。点 P_i の座標は (X_i,Y_i) です。

正整数 p,q が与えられます。 線分 P_iP_j を p:q に内分する点を Q_{i,j} とします。特に P_i=P_j ならば Q_{i,j}=P_i です。

1 \leq i \lt j \leq N を満たすすべての正整数組 (i,j) に対する Q_{i,j} についての凸包の面積を求めてください。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq p \lt q \leq 10
  • |X_i|\leq 10^7
  • |Y_i|\leq 10^7
  • 入力はすべて整数

入力

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

N p q
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

本問題の制約下で求める凸包の面積は有理数になることが証明できる。 その面積を既約分数で \dfrac{x}{y}\ (x \geq 0, y \geq 1) と表したとき、x,y をこの順に空白区切りで一行で出力せよ。


入力例 1

4 1 2
-2 4
1 1
-3 -2
4 0

出力例 1

59 6

Q_{1,2}=\left(-1,3\right),Q_{1,3}=\left(-\frac{7}{3},2\right),Q_{1,4}=\left(0,\frac{8}{3}\right),Q_{2,3}=\left(-\frac{1}{3},0\right),Q_{2,4}=\left(2,\frac{2}{3}\right),Q_{3,4}=\left(-\frac{2}{3},-\frac{4}{3}\right) です。

これらの凸包は Q_{1,2},Q_{1,3},Q_{3,4},Q_{2,4},Q_{1,4} をこの順に結んだ五角形で、面積は \frac{59}{6} です。


入力例 2

3 3 4
11 -7
2 8
-4 18

出力例 2

0 1

凸包の面積が 0 であることもあります。


入力例 3

10 5 7
-3677189 -8603516
3324282 8371380
-4445534 -865546
-1235744 -6761030
2732080 -9194939
8510740 4384715
-7326815 2451526
-2079912 1054509
2072791 -8408897
-4437202 -5184973

出力例 3

6746232144385823 48

Score : 625 points

Problem Statement

There are N points P_1,P_2,\dots,P_N on the coordinate plane. The coordinates of point P_i are (X_i,Y_i).

You are given positive integers p,q. Let Q_{i,j} be the point that internally divides the segment P_iP_j in the ratio p:q. In particular, if P_i=P_j, then Q_{i,j}=P_i.

Find the area of the convex hull of Q_{i,j} for all pairs of positive integers (i,j) satisfying 1 \leq i \lt j \leq N.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq p \lt q \leq 10
  • |X_i|\leq 10^7
  • |Y_i|\leq 10^7
  • All input values are integers.

Input

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

N p q
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

It can be proved that, under the constraints of this problem, the area of the convex hull to be found is rational. When the area is represented as an irreducible fraction \dfrac{x}{y}\ (x \geq 0, y \geq 1), output x and y in this order, separated by a space, in one line.


Sample Input 1

4 1 2
-2 4
1 1
-3 -2
4 0

Sample Output 1

59 6

We have Q_{1,2}=\left(-1,3\right),Q_{1,3}=\left(-\frac{7}{3},2\right),Q_{1,4}=\left(0,\frac{8}{3}\right),Q_{2,3}=\left(-\frac{1}{3},0\right),Q_{2,4}=\left(2,\frac{2}{3}\right),Q_{3,4}=\left(-\frac{2}{3},-\frac{4}{3}\right).

Their convex hull is the pentagon formed by connecting Q_{1,2},Q_{1,3},Q_{3,4},Q_{2,4},Q_{1,4} in this order, and its area is \frac{59}{6}.


Sample Input 2

3 3 4
11 -7
2 8
-4 18

Sample Output 2

0 1

The area of the convex hull may be 0.


Sample Input 3

10 5 7
-3677189 -8603516
3324282 8371380
-4445534 -865546
-1235744 -6761030
2732080 -9194939
8510740 4384715
-7326815 2451526
-2079912 1054509
2072791 -8408897
-4437202 -5184973

Sample Output 3

6746232144385823 48