A - Range Product

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

整数 a，b (a≤b) が与えられます。 a，a+1，...，b すべての積が、正か、負か、0 かを判定してください。

制約

  • a，b は整数である。
  • -10^9≤a≤b≤10^9

部分点

  • 100 点分のデータセットでは、-10≤a≤b≤10 が成り立つ。

入力

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

a b

出力

a，a+1，...，b すべての積が、正ならば Positive を、負ならば Negative を、0 ならば Zero を出力せよ。

入力例1

1 3

出力例1

Positive

1×2×3=6 は正です。

入力例2

-3 -1

出力例2

Negative

(-3)×(-2)×(-1)=-6 は負です。

入力例3

-1 1

出力例3

Zero

(-1)×0×1=0 です。

Problem Statement

You are given two integers a and b (a≤b). Determine if the product of the integers a, a+1, …, b is positive, negative or zero.

Constraints

  • a and b are integers.
  • -10^9≤a≤b≤10^9

Partial Score

  • In test cases worth 100 points, -10≤a≤b≤10.

Input

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

a b

Output

If the product is positive, print Positive. If it is negative, print Negative. If it is zero, print Zero.

Sample Input 1

1 3

Sample Output 1

Positive

1×2×3=6 is positive.

Sample Input 2

-3 -1

Sample Output 2

Negative

(-3)×(-2)×(-1)=-6 is negative.

Sample Input 3

-1 1

Sample Output 3

Zero

(-1)×0×1=0.
B - Box and Ball

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N 個の箱があります。 箱は 1 から N まで番号が振られています。 最初、1 番目の箱には赤いボールが 1 個入っています。 また、2～N 番目の箱には白いボールが 1 個ずつ入っています。

高橋君は M 回の操作を順に行います。 i 回目の操作では、x_i 番目の箱から適当なボールを 1 個選び、それを y_i 番目の箱へ移します。

高橋君がすべての操作を終えた後、赤いボールが入っている可能性のある箱は何個か求めてください。

制約

  • 2≤N≤10^5
  • 1≤M≤10^5
  • 1≤x_i，y_i≤N
  • x_i≠y_i
  • i 回目の操作の直前、x_i 番目の箱には 1 個以上のボールが入っている。

入力

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

N M
x_1 y_1
:
x_M y_M

出力

高橋君がすべての操作を終えた後、赤いボールが入っている可能性のある箱は何個か出力せよ。

入力例1

3 2
1 2
2 3

出力例1

2

1 回目の操作の後、1 番目の箱にはボールが入っておらず、2 番目の箱には赤いボールと白いボールが 1 個ずつ入っており、3 番目の箱には白いボールが 1 個入っています。

2 回目の操作で赤いボールを選んだ場合、赤いボールは 3 番目の箱へ移ります。 2 回目の操作で白いボールを選んだ場合、赤いボールは 2 番目の箱に残ります。

入力例2

3 3
1 2
2 3
2 3

出力例2

1

すべてのボールが 3 番目の箱へ集まります。

入力例3

4 4
1 2
2 3
4 1
3 4

出力例3

3

Problem Statement

We have N boxes, numbered 1 through N. At first, box 1 contains one red ball, and each of the other boxes contains one white ball.

Snuke will perform the following M operations, one by one. In the i-th operation, he randomly picks one ball from box x_i, then he puts it into box y_i.

Find the number of boxes that may contain the red ball after all operations are performed.

Constraints

  • 2≤N≤10^5
  • 1≤M≤10^5
  • 1≤x_i,y_i≤N
  • x_i≠y_i
  • Just before the i-th operation is performed, box x_i contains at least 1 ball.

Input

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

N M
x_1 y_1
:
x_M y_M

Output

Print the number of boxes that may contain the red ball after all operations are performed.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

2

Just after the first operation, box 1 is empty, box 2 contains one red ball and one white ball, and box 3 contains one white ball.

Now, consider the second operation. If Snuke picks the red ball from box 2, the red ball will go into box 3. If he picks the white ball instead, the red ball will stay in box 2. Thus, the number of boxes that may contain the red ball after all operations, is 2.

Sample Input 2

3 3
1 2
2 3
2 3

Sample Output 2

1

All balls will go into box 3.

Sample Input 3

4 4
1 2
2 3
4 1
3 4

Sample Output 3

3
C - Knot Puzzle

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N 本のロープがあります。 ロープは 1 から N まで番号が振られています。 ロープ i の長さは a_i です。

最初、1≤i≤N-1 について、ロープ i の右端とロープ i+1 の左端が結ばれています。 高橋君は次の操作を N-1 回行い、すべての結び目をほどこうとしています。

  • ひと繋がりのロープのうち、長さの総和が L 以上のものをひとつ選ぶ。 選んだひと繋がりのロープに結び目があれば、結び目のうちどれかひとつをほどく。

高橋君は結び目をほどく順番を工夫し、すべての結び目をほどくことができるでしょうか？ 可能か判定し、可能ならば結び目をほどく順番をひとつ求めてください。

制約

  • 2≤N≤10^5
  • 1≤a_i≤10^9
  • 1≤L≤10^9
  • 入力はすべて整数である。

入力

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

N L
a_1 a_2 ... a_N

出力

すべての結び目をほどくことができないならば、Impossible を出力せよ。

すべての結び目をほどくことができるならば、Possible を出力した後、N-1 行出力せよ。 このうち j 行目には、j 回目の操作でほどく結び目の番号を出力せよ。 ただし、ロープ i の右端とロープ i+1 の左端を結ぶものを結び目 i とする。

入力例1

3 50
30 20 10

出力例1

Possible
2
1

先に結び目 1 をほどくと、結び目 2 をほどけなくなってしまいます。

入力例2

2 21
10 10

出力例2

Impossible

入力例3

5 50
10 20 30 40 50

出力例3

Possible
1
2
3
4

他に例えば、3，4，1，2 の順に出力しても正解となります。

Problem Statement

We have N pieces of ropes, numbered 1 through N. The length of piece i is a_i.

At first, for each i (1≤i≤N-1), piece i and piece i+1 are tied at the ends, forming one long rope with N-1 knots. Snuke will try to untie all of the knots by performing the following operation repeatedly:

  • Choose a (connected) rope with a total length of at least L, then untie one of its knots.

Is it possible to untie all of the N-1 knots by properly applying this operation? If the answer is positive, find one possible order to untie the knots.

Constraints

  • 2≤N≤10^5
  • 1≤L≤10^9
  • 1≤a_i≤10^9
  • All input values are integers.

Input

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

N L
a_1 a_2 ... a_n

Output

If it is not possible to untie all of the N-1 knots, print Impossible.

If it is possible to untie all of the knots, print Possible, then print another N-1 lines that describe a possible order to untie the knots. The j-th of those N-1 lines should contain the index of the knot that is untied in the j-th operation. Here, the index of the knot connecting piece i and piece i+1 is i.

If there is more than one solution, output any.

Sample Input 1

3 50
30 20 10

Sample Output 1

Possible
2
1

If the knot 1 is untied first, the knot 2 will become impossible to untie.

Sample Input 2

2 21
10 10

Sample Output 2

Impossible

Sample Input 3

5 50
10 20 30 40 50

Sample Output 3

Possible
1
2
3
4

Another example of a possible solution is 3, 4, 1, 2.
D - Stamp Rally

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N 頂点 M 辺の無向グラフがあります。 頂点は 1 から N まで番号が振られています。 辺は 1 から M まで番号が振られています。 辺 i は頂点 a_i と b_i を結んでいます。 グラフは連結です。

このグラフの上で、Q 組の兄弟がスタンプラリーをします。 j 組目の兄弟は次のようなスタンプラリーをします。

  • 最初、兄は頂点 x_j に、弟は頂点 y_j にいる。
  • 兄弟でちょうど z_j 個の頂点を訪れる。 ただし、同一の頂点を兄弟ともに訪れた場合でも、2 個の頂点を訪れたとは見なさない。
  • 兄または弟が通った辺の番号の最大値がスコアとなる。 兄弟はこのスコアをできるだけ小さくする。

それぞれの兄弟のスコアを求めてください。

制約

  • 3≤N≤10^5
  • N-1≤M≤10^5
  • 1≤a_i＜b_i≤N
  • グラフは連結である。
  • 1≤Q≤10^5
  • 1≤x_j＜y_j≤N
  • 3≤z_j≤N

入力

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

N M
a_1 b_1
a_2 b_2
:
a_M b_M
Q
x_1 y_1 z_1
x_2 y_2 z_2
:
x_Q y_Q z_Q

出力

Q 行出力せよ。 j 行目には、j 組目の兄弟のスコアを出力せよ。

入力例1

5 6
2 3
4 5
1 2
1 3
1 4
1 5
6
2 4 3
2 4 4
2 4 5
1 3 3
1 3 4
1 3 5

出力例1

1
2
3
1
5
5

Problem Statement

We have an undirected graph with N vertices and M edges. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i connects vertices a_i and b_i. The graph is connected.

On this graph, Q pairs of brothers are participating in an activity called Stamp Rally. The Stamp Rally for the i-th pair will be as follows:

  • One brother starts from vertex x_i, and the other starts from vertex y_i.
  • The two explore the graph along the edges to visit z_i vertices in total, including the starting vertices. Here, a vertex is counted only once, even if it is visited multiple times, or visited by both brothers.
  • The score is defined as the largest index of the edges traversed by either of them. Their objective is to minimize this value.

Find the minimum possible score for each pair.

Constraints

  • 3≤N≤10^5
  • N−1≤M≤10^5
  • 1≤a_i<b_i≤N
  • The given graph is connected.
  • 1≤Q≤10^5
  • 1≤x_j<y_j≤N
  • 3≤z_j≤N

Input

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

N M
a_1 b_1
a_2 b_2
:
a_M b_M
Q
x_1 y_1 z_1
x_2 y_2 z_2
:
x_Q y_Q z_Q

Output

Print Q lines. The i-th line should contain the minimum possible score for the i-th pair of brothers.

Sample Input 1

5 6
2 3
4 5
1 2
1 3
1 4
1 5
6
2 4 3
2 4 4
2 4 5
1 3 3
1 3 4
1 3 5

Sample Output 1

1
2
3
1
5
5
E - Candy Piles

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

キャンディの山が N 個あります。 山は 1 から N まで番号が振られています。 最初、i 番目の山には a_i 個のキャンディがあります。

高橋君と青木君がゲームで勝負します。 高橋君と青木君は交互に、次の 2 種類の操作のどちらかを行います。 高橋君が先手です。

  • キャンディが最も多く残っている山をひとつ選び、その山のキャンディをすべて食べる。
  • キャンディが残っているすべての山から、1 個ずつキャンディを食べる。

全体で最後のキャンディを食べた人が負けです。 二人が最適に行動したとき、どちらが勝つかを判定してください。

制約

  • 1≤N≤10^5
  • 1≤a_i≤10^9

入力

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

N
a_1 a_2 ... a_N

出力

先手の高橋君が勝つならば First を、後手の青木君が勝つならば Second を出力せよ。

入力例1

2
1 3

出力例1

First

キャンディが最も多いのは 2 番目の山です。 高橋君が 2 番目の山のキャンディをすべて食べると、青木君は最後のキャンディを食べるしかありません。

入力例2

3
1 2 1

出力例2

First

高橋君がすべての山から 1 個ずつキャンディを食べると、青木君は最後のキャンディを食べるしかありません。

入力例3

3
1 2 3

出力例3

Second

Problem Statement

There are N piles of candies on the table. The piles are numbered 1 through N. At first, pile i contains a_i candies.

Snuke and Ciel are playing a game. They take alternating turns. Snuke goes first. In each turn, the current player must perform one of the following two operations:

  1. Choose a pile with the largest number of candies remaining, then eat all candies of that pile.
  2. From each pile with one or more candies remaining, eat one candy.

The player who eats the last candy on the table, loses the game. Determine which player will win if both players play the game optimally.

Constraints

  • 1≤N≤10^5
  • 1≤a_i≤10^9

Input

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

N
a_1 a_2 … a_N

Output

If Snuke will win, print First. If Ciel will win, print Second.

Sample Input 1

2
1 3

Sample Output 1

First

At the beginning of the game, pile 2 contains the most candies. If Snuke eats all candies of this pile, Ciel has no choice but to eat the last candy.

Sample Input 2

3
1 2 1

Sample Output 2

First

If Snuke eats one candy from each pile, Ciel is again left with the last candy.

Sample Input 3

3
1 2 3

Sample Output 3

Second
F - Leftmost Ball

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

色 1，2，...，N のボールがそれぞれ K 個ずつあります。 高橋君は、これら N×K 個のボールを好きな順番で横一列に並べました。 その後、各色ごとに最も左にあるボールを色 0 へ塗り替えました。

最終的なボールの色の並びは何通り考えられるでしょうか？ 10^9+7 で割った余りを求めてください。

制約

  • 1≤N，K≤2,000

入力

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

N K

出力

最終的なボールの色の並びは何通り考えられるか、10^9+7 で割った余りを出力せよ。

入力例1

2 2

出力例1

4

次の 4 通りです。

  • (0，1，0，2)
  • (0，0，1，2)
  • (0，2，0，1)
  • (0，0，2，1)

入力例2

3 1

出力例2

1

次の 1 通りです。

  • (0，0，0)

入力例3

2 3

出力例3

14

入力例4

2000 2000

出力例4

546381702

Problem Statement

Snuke loves colorful balls. He has a total of N×K balls, K in each of his favorite N colors. The colors are numbered 1 through N.

He will arrange all of the balls in a row from left to right, in arbitrary order. Then, for each of the N colors, he will paint the leftmost ball of that color into color 0, a color different from any of the N original colors.

After painting, how many sequences of the colors of the balls are possible? Find this number modulo 10^9+7.

Constraints

  • 1≤N,K≤2,000

Input

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

N K

Output

Print the number of the possible sequences of the colors of the balls after painting, modulo 10^9+7.

Sample Input 1

2 2

Sample Output 1

4

The following 4 sequences are possible:

  • (0,1,0,2)
  • (0,0,1,2)
  • (0,2,0,1)
  • (0,0,2,1)

Sample Input 2

3 1

Sample Output 2

1

The following 1 sequence is possible:

  • (0,0,0)

Sample Input 3

2 3

Sample Output 3

14

Sample Input 4

2000 2000

Sample Output 4

546381702