第五回アルゴリズム実技検定過去問

A - OX Game

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 9 点

注意

この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

以下のルールで○✕ゲームが行われています。

まず、縦 1 マス、横 5 マスのマス目を作る。
全てのマスに o または x を書き込む。
o が横に連続して 3 つ以上並んでいるなら、 o の勝ちである。
そうでなくて、 x が横に連続して 3 つ以上並んでいるなら、 x の勝ちである。
このどちらでもない場合、引き分けである。

書き込みが終わった後のマス目の状態が与えられます。左から i 番目のマスに書かれた記号は S_i です。
○✕ゲームの結果を判定してください。

制約

S_i は o または x

入力

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

S_1S_2S_3S_4S_5

出力

o の勝ちならば o を、 x の勝ちならば x を、引き分けならば draw を出力せよ。

入力例 1

xooox

出力例 1

o が連続して 3 つ並んでいるので、 o の勝ちです。

入力例 2

xxxxx

出力例 2

x が連続して 5 つ並んでいるので、 x の勝ちです。

入力例 3

xoxxo

出力例 3

draw

o も x も 3 つ以上連続して並んでいないため、引き分けです。

Score : 9 points

Warning

Do not make any mention of this problem until December 27, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Two persons are playing "OX Game" in the following manner:

They draw a horizontal row of five squares.
They write o or x in each square.
If there are three or more consecutive os, the player o wins.
Otherwise, if there are three or more consecutive xs, the player x wins.
If neither of the above holds, the game is drawn.

You are given the state of the row of squares after the persons write symbols; the symbol written in the i-th square from the left is S_i.
Determine the winner of the game.

Constraints

S_i is o or x.

Input

Input is given from Standard Input in the following format:

S_1S_2S_3S_4S_5

Output

If the player o wins, print o; if the player x wins, print x; if the game is drawn, print draw.

Sample Input 1

xooox

Sample Output 1

We have three consecutive os, so the player o wins.

Sample Input 2

xxxxx

Sample Output 2

We have five consecutive xs, so the player x wins.

Sample Input 3

xoxxo

Sample Output 3

draw

We have neither three consecutive os nor three consecutive xs, so the game is drawn.

B - Overwrite

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 8 点

注意

問題文

英小文字からなる長さ N の文字列 S が与えられます。
また、文字列 T があり、 T ははじめ空文字列です。

あなたは以下の操作を i = 1, 2, \dots, N に対して、 i = 1 から順に行います。

S の左から i 番目の文字を c とする。 T から c と同じ文字を全て削除した後、 T の末尾に c を追加する。

操作が終わった後の T を求めてください。

制約

1 \le N \le 100
S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

操作が終わった後の T を出力せよ。

入力例 1

3
aba

出力例 1

ba

はじめ、 T は空文字列です。
1 回目の操作では、 T の末尾に a を追加するので a になります。
2 回目の操作では、 T の末尾に b を追加するので ab になります。
3 回目の操作では、 T から a を削除して b にした後、末尾に a を追加するので ba になります。

入力例 2

7
sptaast

出力例 2

past

入力例 3

30
ryfoxchyvfmsewlwpoyvhdjkbvdjsa

出力例 3

rxcfmelwpoyhkbvdjsa

Score : 8 points

Warning

Problem Statement

Given is a string S of length N consisting of lowercase English letters.
We also have a string T, which is initially empty.

For each i = 1, 2, \dots, N in this order, you will do the following operation:

Let c be the i-th character from the left. Delete all occurrences of c from T, and then add c at the end of T.

Find the string T after all the operations.

Constraints

1 \le N \le 100
S is a string of length N consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the string T after all the operations.

Sample Input 1

3
aba

Sample Output 1

ba

Initially, T is empty.
In the first operation, we add a at the end of T, making it a.
In the second operation, we add b at the end of T, making it ab.
In the third operation, we delete a from T, making it b, and then add a at the end, making it ba.

Sample Input 2

7
sptaast

Sample Output 2

past

Sample Input 3

30
ryfoxchyvfmsewlwpoyvhdjkbvdjsa

Sample Output 3

rxcfmelwpoyhkbvdjsa

C - Hexatridecimal

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 8 点

注意

問題文

16 進法では、一般的に 0123456789ABCDEF の 16 個の数字を使って 1 つの桁を表しますが、 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ の 36 個の数字を使う 36 進法を考えます。
36 進法では、0 の次は 1 、 9 の次は \rm A 、\rm Z の次は 10 になります。整数 N が 10 進表記で与えられるので、 36 進表記に変換してください。

制約

N は整数
0 \le N \lt 36^3

入力

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

出力

N を 36 進表記で出力せよ。

入力例 1

出力例 1

3F

\rm 123=3\times36^1+15(F)\times36^0 です。

入力例 2

出力例 2

1S0

\rm 2304=1\times36^2+28(S)\times36^1 です。

入力例 3

出力例 3

Score : 8 points

Warning

Problem Statement

In base 16, a digit is represented by one of the 16 symbols: 0123456789ABCDEF.
Here, let us consider base 36, which uses 36 symbols: 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ.
In base 36, 0 precedes 1, 9 precedes \rm A, and \rm Z precedes 10. Given an integer N in base 10, convert it to base 36.

Constraints

N is an integer.
0 \le N \lt 36^3

Input

Input is given from Standard Input in the following format:

Output

Print N in base 36.

Sample Input 1

Sample Output 1

3F

We have \rm 123=3\times36^1+15(F)\times36^0.

Sample Input 2

Sample Output 2

1S0

We have \rm 2304=1\times36^2+28(S)\times36^1.

Sample Input 3

Sample Output 3

D - Leading Zeros

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 7 点

注意

問題文

N 個の文字列 S_i が与えられます。S_i は数字のみからなる文字列です。

これらの文字列を 10 進法の数とみなして、値の小さい順にソートして出力してください。ただし、値が等しい数は、先頭につく 0 の個数が多い方を前にしてください。

制約

1\leq N \leq 10^5
S_i の長さの和は 10^5 以下
S_i は数字のみからなる

入力

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

N
S_1
\vdots
S_N

出力

与えられた文字列を指定された順序にソートし、改行区切りで出力せよ。

入力例 1

出力例 1

S_2,S_3,S_4 はいずれも値としては 1 ですが、先頭につく 0 の個数が多いものから順に出力してください。

入力例 2

6
1111111111111111111111
00011111111111111111111
000000111111111111111111
0000000001111111111111111
00000000000011111111111111
000000000000000111111111111

出力例 2

000000000000000111111111111
00000000000011111111111111
0000000001111111111111111
000000111111111111111111
00011111111111111111111
1111111111111111111111

与えられる文字列は非常に長い可能性があります。

Score : 7 points

Problem Statement

Given are N strings S_1, \ldots, S_N, each of which consists of digits.

Sort these strings as decimal integers in ascending order and print the result. If multiple strings are equal as integers, they should be in descending order of the numbers of leading zeros.

Constraints

1\leq N \leq 10^5
The total length of S_i is at most 10^5.
S_i consists of digits.

Input

Input is given from Standard Input in the following format:

N
S_1
\vdots
S_N

Output

Print the strings after sorting them in the specified order, each in its own line.

Sample Input 1

Sample Output 1

As integers, S_2, S_3, and S_4 are all 1, but we ask you to print them in descending order of the numbers of leading zeros.

Sample Input 2

6
1111111111111111111111
00011111111111111111111
000000111111111111111111
0000000001111111111111111
00000000000011111111111111
000000000000000111111111111

Sample Output 2

000000000000000111111111111
00000000000011111111111111
0000000001111111111111111
000000111111111111111111
00011111111111111111111
1111111111111111111111

There may be extremely long strings.

E - Stamp

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 7 点

注意

問題文

H 行 W 列のマス目 S があり、上から i 行目、左から j 列目のマスをマス (i, j) と呼ぶことにします。
いくつかのマスには障害物が置かれているかもしれません。S_{i, j} が # ならマス (i, j) には障害物があり、. ならありません。

また、あなたはハンコを一つ持っています。このハンコの底面は H 行 W 列のマス目 T のいくつかのマスで構成される形をしています。
具体的には、このハンコの底面は T_{i, j} が # であるようなマス (i, j) のみを取り出してできる図形をしています。
ここで、ハンコの底面を構成するマスはひとつながりです。つまり、T_{i, j} が # であるようなマス (i, j) を「有効なマス」と呼ぶと、どの二つの有効なマスも、辺を共有するマスへ移動することを繰り返し、有効なマスだけを通って行き来できます。

ハンコは移動したり、回転したりできます。以下の条件を満たすようにマス目 S にハンコの底面を重ねることができるかを判定してください。

ハンコの底面を構成するマスの辺は全て、マス目 S のマスのいずれかの辺と平行である
ハンコの底面はマス目 S からはみ出していない
ハンコの底面は障害物が置かれているマスに重なっていない

制約

1 \le H \le 10
1 \le W \le 10
S_{i, j} は # または .
T_{i, j} は # または .
T_{i, j} が # であるようなマス (i, j) はひとつながりである
少なくとも一つ S_{i, j} が . であるような i, j が存在する
少なくとも一つ T_{i, j} が # であるような i, j が存在する

入力

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

H W
S_{1, 1}S_{1, 2}S_{1, 3}\dots S_{1, W}
S_{2, 1}S_{2, 2}S_{2, 3}\dots S_{2, W}
S_{3, 1}S_{3, 2}S_{3, 3}\dots S_{3, W}
\hspace{40pt} \vdots
S_{H, 1}S_{H, 2}S_{H, 3}\dots S_{H, W}
T_{1, 1}T_{1, 2}T_{1, 3}\dots T_{1, W}
T_{2, 1}T_{2, 2}T_{2, 3}\dots T_{2, W}
T_{3, 1}T_{3, 2}T_{3, 3}\dots T_{3, W}
\hspace{40pt} \vdots
T_{H, 1}T_{H, 2}T_{H, 3}\dots T_{H, W}

出力

問題文の条件を満たすようにハンコを重ねることができるなら Yes を、そうでないなら No を出力せよ。

入力例 1

3 3
...
.#.
..#
#.#
###
...

出力例 1

Yes

ハンコを回転させて、下図のように重ねると条件を満たします。緑色がハンコの底面がある部分で、灰色が障害物が置かれているマスを表します。

入力例 2

3 3
...
#..
#.#
.#.
.##
##.

出力例 2

No

回転と移動だけではどうやっても条件を満たすように重ねることはできません。

入力例 3

2 5
.....
..#..
..##.
.###.

出力例 3

Yes

以下のように重ねるとよいです。

Score : 7 points

Warning

Problem Statement

We have a grid S with H rows and W columns of squares. Let Square (i, j) denote the square at the i-th row from the top and j-th column from the left.
Some of the squares may contain obstacles.
Square (i, j) contains an obstacle if S_{i, j} is #, and it does not contain one if S_{i, j} is ..

You have a stamp whose shape is formed of squares in a grid T with H rows and W columns. More specifically, the shape of the stamp is formed of the squares (i, j) such that T_{i, j} is #.
Here, the squares that form the stamp are connected. In other words: let us call Square (i, j) valid when T_{i, j} is #. We can then travel between any two valid squares by repeatedly moving up, down, left, or right to a valid square.

You can move the stamp to any position you like and rotate it. Determine whether it is possible to position the stamp on the grid S so that the following conditions are satisfied:

the edges of the squares forming the stamp are all parallel to some of the edges of the squares in the grid S;
the stamp does not stick out of the grid S;
the stamp does not occupy a square containing an obstacle.

Constraints

1 \le H \le 10
1 \le W \le 10
H and W are integers.
S_{i, j} is # or ..
T_{i, j} is # or ..
The squares (i, j) such that T_{i, j} is # are connected.
S_{i, j} is . for at least one pair (i, j).
T_{i, j} is . for at least one pair (i, j).

Input

Input is given from Standard Input in the following format:

H W
S_{1, 1}S_{1, 2}S_{1, 3}\dots S_{1, W}
S_{2, 1}S_{2, 2}S_{2, 3}\dots S_{2, W}
S_{3, 1}S_{3, 2}S_{3, 3}\dots S_{3, W}
\hspace{40pt} \vdots
S_{H, 1}S_{H, 2}S_{H, 3}\dots S_{H, W}
T_{1, 1}T_{1, 2}T_{1, 3}\dots T_{1, W}
T_{2, 1}T_{2, 2}T_{2, 3}\dots T_{2, W}
T_{3, 1}T_{3, 2}T_{3, 3}\dots T_{3, W}
\hspace{40pt} \vdots
T_{H, 1}T_{H, 2}T_{H, 3}\dots T_{H, W}

Output

If it is possible to position the stamp so that the conditions are all satisfied, print Yes; otherwise, print No.

Sample Input 1

3 3
...
.#.
..#
#.#
###
...

Sample Output 1

Yes

We can rotate the stamp and move it to the position shown in the figure below to satisfy the conditions. In the figure, the green part represents the stamp, and the gray squares contain obstacles.

Sample Input 2

3 3
...
#..
#.#
.#.
.##
##.

Sample Output 2

No

It is impossible to position the stamp to satisfy the conditions by just moving and rotating it.

Sample Input 3

2 5
.....
..#..
..##.
.###.

Sample Output 3

Yes

We can position the stamp as follows:

F - Dangerous Chemicals

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 7 点

注意

問題文

薬品が N 種類あり、薬品 1 から薬品 N まで番号付けされています。あなたは、これらのうち 1 種類以上を選んで混ぜ、新たな物質を作ります。
これらの薬品は危険なため、混ぜ方によっては爆発することがあります。
1 \le i \le M を満たす整数 i が存在して、薬品 A_i, B_i, C_i の 3 種類の薬品が全て混ぜられているとき、爆発します。それ以外の場合には爆発しません。
あなたは痛い目を見たくないので、直ちに爆発するような混ぜ方はしません。しかし、できる限り爆発寸前の物質を作りたいので、「物質に薬品 x を新たに追加すると爆発するような薬品 x の数」をできる限り大きくしようとします。
この数として考えられる最大の値を求めてください。

制約

3 \le N \le 14
1 \le M \le \frac{N(N - 1)(N - 2)}{6}
1 \le A_i \lt B_i \lt C_i \le N
(A_i, B_i, C_i) \neq (A_j, B_j, C_j) (i \neq j)
入力は全て整数

入力

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

N M
A_1 B_1 C_1
A_2 B_2 C_2
A_3 B_3 C_3
\hspace{25pt} \vdots
A_M B_M C_M

出力

作る物質に新たに追加すると爆発するような薬品の数として考えられる最大値を出力せよ。

入力例 1

4 2
1 2 3
1 2 4

出力例 1

薬品 1 と薬品 2 を選んで混ぜると、直ちに爆発はせず、薬品 3, 4 のどちらを追加しても爆発するので、「物質に新たに追加すると爆発するような薬品の種類数」が 2 となります。
この数をこれより大きくすることはできないので答えは 2 です。

入力例 2

出力例 2

薬品 2 と薬品 5 を選んで混ぜると、薬品 1, 3, 4, 6 全てが「新たに追加すると爆発するような薬品」となります。

入力例 3

5 1
1 2 3

出力例 3

Score : 7 points

Warning

Problem Statement

We have N chemicals, labeled Chemical 1 through Chemical N. You will choose one or more of these chemicals and mix them to make a new substance.
These dangerous chemicals can explode if mixed wrongly.
More specifically, if there is an integer i (1 \le i \le M) such that the chemicals A_i, B_i, and C_i are all used in the mixture, they will explode; otherwise, no explosion happens.
You will not mix chemicals in a way that results in an immediate explosion, which hurts. However, you do want to make a substance that is as close to an explosion as possible, so you want to make the following count as large as possible: the number of chemicals x that results in an explosion if Chemical x is added to the substance.
Find the maximum possible value of this count.

Constraints

3 \le N \le 14
1 \le M \le \frac{N(N - 1)(N - 2)}{6}
1 \le A_i \lt B_i \lt C_i \le N
(A_i, B_i, C_i) \neq (A_j, B_j, C_j) (i \neq j)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
A_2 B_2 C_2
A_3 B_3 C_3
\hspace{25pt} \vdots
A_M B_M C_M

Output

Print the maximum possible number of chemicals x that results in an explosion if Chemical x is added to the substance you make.

Sample Input 1

4 2
1 2 3
1 2 4

Sample Output 1

If we choose Chemical 1 and 2 and mix them, they do not immediately explode, but adding either Chemical 3 or 4 results in an explosion, which means the count in question is 2.
It is impossible to make this count larger, so the answer is 2.

Sample Input 2

Sample Output 2

If we choose Chemical 2 and 5, adding any one of Chemicals 1, 3, 4, and 6 results in an explosion.

Sample Input 3

5 1
1 2 3

Sample Output 3

G - Snake

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

問題文

H 行 W 列のマス目があり、上から i 行目、左から j 列目のマスをマス (i, j) と呼ぶことにします。
このマス目上にヘビがいます。ヘビの位置は、正整数 k と、k 個のマスの座標の列、(x_1, y_1), (x_2, y_2), (x_3, y_3), \dots, (x_k, y_k) で表され、以下の条件を満たします。

1 \le x_i \le H
1 \le y_i \le W
(x_i, y_i) \neq (x_j, y_j) (i \neq j)
マス (x_i, y_i) とマス (x_{i + 1}, y_{i + 1}) は辺を共有して隣接している

マス目上のどのマスをヘビが占領しているかが与えられます。具体的には、ある整数 i (1 \le i \le k) が存在して (x_i, y_i) = (a, b) であるならば、 S_{a, b} は # であり、そうでないなら . です。
k 及び (x_1, y_1), (x_2, y_2), (x_3, y_3), \dots, (x_k, y_k) として考えられるものを一つ求めてください。

制約

1 \le H \le 4
1 \le W \le 4
S_{i, j} は # または .
問題文の状況と合致する k と (x_1, y_1), (x_2, y_2), (x_3, y_3), \dots, (x_k, y_k) が存在する

入力

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

H W
S_{1, 1}S_{1, 2}S_{1, 3} \dots S_{1, W}
S_{2, 1}S_{2, 2}S_{2, 3} \dots S_{2, W}
S_{3, 1}S_{3, 2}S_{3, 3} \dots S_{3, W}
\hspace{40pt} \vdots
S_{H, 1}S_{H, 2}S_{H, 3} \dots S_{H, W}

出力

まず 1 行目に k を出力せよ。
次に 2 行目から k + 1 行目にかけて、1 + i 行目には x_i と y_i をこの順に空白区切りで出力せよ。
問題文の状況と合致する出力内容であればどれを出力しても正解となる。

入力例 1

3 3
##.
.##
###

出力例 1

これを反転した列も正解となります。

入力例 2

3 4
####
####
.#..

出力例 2

これと、これを反転したもの以外にもいくつか正解はあります。

入力例 3

3 3
.##
###
###

出力例 3

Score : 6 points

Warning

Problem Statement

We have a grid S with H rows and W columns of squares. Let Square (i, j) denote the square at the i-th row from the top and j-th column from the left.
There is a snake on this grid. Its position is represented by a positive integer k and a sequence of k pairs of coordinates (x_1, y_1), (x_2, y_2), (x_3, y_3), \dots, (x_k, y_k) satisfying the following conditions:

1 \le x_i \le H;
1 \le y_i \le W;
(x_i, y_i) \neq (x_j, y_j) (i \neq j);
Square (x_i, y_i) and Square (x_{i + 1}, y_{i + 1}) are adjacent, sharing an edge.

You are given the set of squares occupied by the snake. More specifically, S_{a, b} is # if there is an integer i (1 \le i \le k) such that (x_i, y_i) = (a, b), and S_{a, b} is . otherwise.
Find one possible combination of k and the sequence (x_1, y_1), (x_2, y_2), (x_3, y_3), \dots, (x_k, y_k).

Constraints

1 \le H \le 4
1 \le W \le 4
S_{i, j} is # or ..
There exist an integer k and a sequence (x_1, y_1), (x_2, y_2), (x_3, y_3), \dots, (x_k, y_k) that are consistent with the situation.

Input

Input is given from Standard Input in the following format:

H W
S_{1, 1}S_{1, 2}S_{1, 3} \dots S_{1, W}
S_{2, 1}S_{2, 2}S_{2, 3} \dots S_{2, W}
S_{3, 1}S_{3, 2}S_{3, 3} \dots S_{3, W}
\hspace{40pt} \vdots
S_{H, 1}S_{H, 2}S_{H, 3} \dots S_{H, W}

Output

In the first line, print the integer k.
In each of the second through (k + 1)-th lines, print the coordinates; the (1 + i)-th line should contain x_i and y_i with a space in between.
Any combination of an integer and a sequence of coordinates that satisfies the condition will be accepted.

Sample Input 1

3 3
##.
.##
###

Sample Output 1

The reversal of this sequence will also be accepted.

Sample Input 2

3 4
####
####
.#..

Sample Output 2

There are also solutions other than this and its reversal.

Sample Input 3

3 3
.##
###
###

Sample Output 3

H - Conveyor

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

問題文

縦 H マス、横 W マスの 2 次元グリッドがあります。
上から i 行目、左から j 列目のマスをマス (i, j) と表すことにします。
マス (i, j) の情報が文字 s_{i,j} により与えられます。 s_{i,j} は . , # , < , ^ , > , v のいずれかです。 # は入ることのできないマスであることを、 < , ^ , > , v の 4 つは一方通行のマスであることを、 . は何もないマスであることを表します。
あなたは # でないマスを 1 つ選びロボットを置いたあと、以下の操作を繰り返してロボットをマス (r, c) まで動かします。

現在いるマスと上下左右に隣り合う、# でないマスに動かす。このとき、グリッドの外に出てはいけない。

ただし、ロボットが一方通行のマスにいるときはその方向以外には動かすことができません。
より正確には、ロボットがマス (i, j) にいるとき、

s_{i,j} が < ならばマス (i, j - 1) 以外には動かすことができません。
s_{i,j} が ^ ならばマス (i - 1, j) 以外には動かすことができません。
s_{i,j} が > ならばマス (i, j + 1) 以外には動かすことができません。
s_{i,j} が v ならばマス (i + 1, j) 以外には動かすことができません。

# でない各マスについて、そのマスにロボットを置いたときに、ロボットをマス (r, c) まで動かせるかを判定してください。

制約

1 \le H, W
H \times W \le 10^6
1 \le r \le H
1 \le c \le W
s_{i,j} は . , # , < , ^ , > , v のいずれか
s_{r,c} は # でない

入力

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

H W
r c
s_{1,1}\dots s_{1,W}
\vdots
s_{H,1}\dots s_{H,W}

出力

H 行にわたって、 W 文字の文字列を出力せよ。
i 行目の j 文字目には、 s_{i,j} が # である場合 # を、 s_{i,j} が # でない場合、ロボットをマス (i,j) からマス (r, c) まで動かせるならば o を、動かせないならば x を出力せよ。

入力例 1

3 3
1 1
..#
^^.
><.

出力例 1

oo#
ooo
xxo

ロボットをマス (3,3) に置いたとき、 (3,3) \rightarrow (2,3) \rightarrow (2,2) \rightarrow (1,2) \rightarrow (1,1) と動かすことでロボットをマス (1,1) まで移動させることができます。ロボットをマス (3,1) に置くと、一方通行のマスがあるためロボットをマス (1,1) まで移動させることができません。

入力例 2

10 12
9 1
#.^<..><<...
#<>.#<^.<<.^
^.<>.^.^.^>.
^.>#^><#....
.>.^>#...<<>
....^^.#<.<.
.>^..^#><#.^
......#>....
..<#<...^>^.
<..^>^^...^<

出力例 2

#xxxxxxxxxxx
#xxx#xxxxxxx
xooxxxxxxxxx
xox#xxx#xxxx
oooxx#xxxxxx
ooooxxx#xxxx
ooooox#xx#xx
oooooo#xxxxx
ooo#xoooxxxx
xooxooooooxx

入力例 3

15 20
13 9
####..<#^>#>.<<><^..
#.>#>.^#^.>><>...^..
>..<>.#.>.>.>...#..<
<^>.#..<>^#<#.>.<.^.
>#<^>.>#^>#^.^.#^><^
<^.^.#<...<.><#>...#
.<>....^..#>>#..>>><
.<#<^#.>#>^^.>.##.^<
.#.^.....<<#^#><^<<<
^.#>.#^.>.^.^<<>..><
.^#^<^^^<......^>.#^
.<..#>...^>^.^<..<.^
#.^.#..#.....>#.^^.>
.#^..>>><>>>^..#^.^^
.>#..<..<>.#>..^.#.^

出力例 3

####xxx#xx#xxxxxxxxx
#xx#xxx#xxxxxxxxxxxx
xxxxxx#xxxxxxxxx#xxx
xxxx#xxxxx#x#xxxxxxx
x#xxxxx#xx#xxxx#xxxx
xxoxo#xxxxxxxx#xxxx#
xxoooooxxx#xx#xxxxxx
xx#xo#ox#xxxxxx##xxx
x#xxooooooo#x#xxxxxx
xx#oo#ooooooxxxoooxx
xx#ooxoooooooooooo#x
xxoo#oooooooooooooox
#ooo#oo#ooooox#oooox
x#oooxxxxoooooo#ooox
xx#oooooooo#oooxo#ox

Score : 6 points

Warning

Problem Statement

We have a two-dimensional grid with H horizontal rows and W vertical columns.
Let Square (i, j) denote the square at the i-th row from the top and j-th column from the left.
Square (i, j) is described by a character s_{i,j}, which is . , # , < , ^ , > , or v.
# represents a blocked square; each of <, ^, >, and v represents a square on which you can only go one way; . represents an empty square.
You will put a robot on a non-# square of your choice and then repeat the operation below to send the robot to Square (r, c).

Move the robot up, down, left, or right to an adjacent non-# square. The robot is not allowed to go out of the grid.

However, when the robot is on a one-way square, it can only go in the specified direction.
More formally, when a robot is on Square (i, j),

if s_{i,j} is <, the robot can only go to Square (i, j - 1);
if s_{i,j} is ^, the robot can only go to Square (i - 1, j);
if s_{i,j} is >, the robot can only go to Square (i, j + 1);
if s_{i,j} is v, the robot can only go to Square (i + 1, j).

For each non-# square, determine whether the robot can start at that square and reach Square (r, c).

Constraints

1 \le H, W
H \times W \le 10^6
1 \le r \le H
1 \le c \le W
s_{i,j} is ., #, <, ^, >, or v.
s_{r,c} is not #.

Input

Input is given from Standard Input in the following format:

H W
r c
s_{1,1}\dots s_{1,W}
\vdots
s_{H,1}\dots s_{H,W}

Output

Print H lines containing W characters each.
The j-th character in the i-th line should be # if s_{i,j} is #; o if s_{i,j} is not # and the robot can reach from Square (i, j) to Square (r, c); and x if s_{i,j} is not # and the robot cannot reach from Square (i, j) to Square (r, c).

Sample Input 1

3 3
1 1
..#
^^.
><.

Sample Output 1

oo#
ooo
xxo

If the robot starts at Square (3, 3), it can reach (1, 1) as follows: (3,3) \rightarrow (2,3) \rightarrow (2,2) \rightarrow (1,2) \rightarrow (1,1).
On the other hand, if it starts at Square (3, 1), it cannot reach (1, 1) because of the one-way squares.

Sample Input 2

10 12
9 1
#.^<..><<...
#<>.#<^.<<.^
^.<>.^.^.^>.
^.>#^><#....
.>.^>#...<<>
....^^.#<.<.
.>^..^#><#.^
......#>....
..<#<...^>^.
<..^>^^...^<

Sample Output 2

#xxxxxxxxxxx
#xxx#xxxxxxx
xooxxxxxxxxx
xox#xxx#xxxx
oooxx#xxxxxx
ooooxxx#xxxx
ooooox#xx#xx
oooooo#xxxxx
ooo#xoooxxxx
xooxooooooxx

Sample Input 3

15 20
13 9
####..<#^>#>.<<><^..
#.>#>.^#^.>><>...^..
>..<>.#.>.>.>...#..<
<^>.#..<>^#<#.>.<.^.
>#<^>.>#^>#^.^.#^><^
<^.^.#<...<.><#>...#
.<>....^..#>>#..>>><
.<#<^#.>#>^^.>.##.^<
.#.^.....<<#^#><^<<<
^.#>.#^.>.^.^<<>..><
.^#^<^^^<......^>.#^
.<..#>...^>^.^<..<.^
#.^.#..#.....>#.^^.>
.#^..>>><>>>^..#^.^^
.>#..<..<>.#>..^.#.^

Sample Output 3

####xxx#xx#xxxxxxxxx
#xx#xxx#xxxxxxxxxxxx
xxxxxx#xxxxxxxxx#xxx
xxxx#xxxxx#x#xxxxxxx
x#xxxxx#xx#xxxx#xxxx
xxoxo#xxxxxxxx#xxxx#
xxoooooxxx#xx#xxxxxx
xx#xo#ox#xxxxxx##xxx
x#xxooooooo#x#xxxxxx
xx#oo#ooooooxxxoooxx
xx#ooxoooooooooooo#x
xxoo#oooooooooooooox
#ooo#oo#ooooox#oooox
x#oooxxxxoooooo#ooox
xx#oooooooo#oooxo#ox

I - Evacuation Plan

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

問題文

ある都市には村が N 個あり、村 1 から村 N まで番号付けされています。村 i は標高 H_i にあります。どの 2 つの村も同じ標高にはありません。
2 つの村を繋ぐ水路が M 本あり、i 番目の水路は村 A_i と村 B_i を結びます。水路は標高が高い側の村から低い側の村へのみ通行可能です。
この都市では、村 C_1, C_2, C_3, \dots, C_K の K 個の村が災害発生時の避難所として指定されています。
N 個全ての村について、その村から 0 本以上の水路を使っていずれかの避難所に辿りつくことができるか、できるなら最小で何本の水路を通ればよいかを求めてください。

制約

2 \le N \le 2 \times 10^5
1 \le M \le 2 \times 10^5
1 \le K \le N
1 \le H_i \le 10^9
H_i \neq H_j (i \neq j)
1 \le C_i \le N
C_i \neq C_j (i \neq j)
1 \le A_i \le N
1 \le B_i \le N
A_i \neq B_i
(A_i, B_i) \neq (A_j, B_j) (i \neq j)
(A_i, B_i) \neq (B_j, A_j) (i \neq j)
入力は全て整数

入力

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

N M K
H_1 H_2 H_3 \dots H_N
C_1 C_2 C_3 \dots C_K
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_M B_M

出力

N 行に渡って出力せよ。 i 行目には、村 i からいずれかの避難所に辿りつくことができるなら辿りつくのに必要な最小の本数を、辿りつくことができないなら -1 を出力せよ。

入力例 1

出力例 1

村 1 : 村 1 自身が避難所に指定されているので、使用する水路の最小の本数は 0 です。
村 2 : 村 2 自身が避難所に指定されているので、使用する水路の最小の本数は 0 です。
村 3 : 村 3 の方が村 1 より標高が高いので、2 番目の水路を使って避難所に指定されている村 1 に移動することができます。使う水路の本数は 1 で、これが最小です。
村 4 : 村 4 の方が村 2 より標高が高いので、3 番目の水路を使って避難所に指定されている村 2 に移動することができます。使う水路の本数は 1 で、これが最小です。
村 5 : 5 番目の水路を使って村 3 に移動し、更に 2 番目の水路を使って避難所に指定されている村 1 に移動することができます。使う水路の本数は 2 で、これが最小です。

入力例 2

出力例 2

村 5 からはどこにも行くことができず、村 5 自身が避難所に指定されていることもないので、5 行目には -1 を出力します。

入力例 3

出力例 3

Score : 6 points

Warning

Problem Statement

In a city, there are N villages, numbered 1 through N. The elevation of Village i is H_i. No two villages are at the same elevation.
There are M waterways, each of which connects two villages; the i-th waterway connects Village A_i and Village B_i. You can only go through a waterway from the village with the higher elevation to the village with the lower elevation.
In this city, K of the villages - Villages C_1, C_2, C_3, \dots, C_K - are specified as places of refuge in times of disaster.
For each village, determine whether it is possible to reach one of the places of refuge using zero or more waterways. If it is possible, also find the minimum number of waterways that must be traversed to reach a place of refuge from that village.

Constraints

2 \le N \le 2 \times 10^5
1 \le M \le 2 \times 10^5
1 \le K \le N
1 \le H_i \le 10^9
H_i \neq H_j (i \neq j)
1 \le C_i \le N
C_i \neq C_j (i \neq j)
1 \le A_i \le N
1 \le B_i \le N
A_i \neq B_i
(A_i, B_i) \neq (A_j, B_j) (i \neq j)
(A_i, B_i) \neq (B_j, A_j) (i \neq j)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K
H_1 H_2 H_3 \dots H_N
C_1 C_2 C_3 \dots C_K
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_M B_M

Output

Print N lines. If a place of refuge is reachable from Village i, the i-th line should contain the minimum number of waterways that must be traversed to reach a place of refuge; otherwise, the line should contain -1.

Sample Input 1

Sample Output 1

Village 1: since it is a place of refuge itself, the minimum number of waterways that must be traversed is 0.
Village 2: since it is a place of refuge itself, the minimum number of waterways that must be traversed is 0.
Village 3: since its elevation is higher than that of Village 1, we can traverse the 2-nd waterway to go to Village 1, which is a place of refuge. We have traversed 1 waterway, which is the minimum number needed.
Village 4: since its elevation is higher than that of Village 2, we can traverse the 3-rd waterway to go to Village 2, which is a place of refuge. We have traversed 1 waterway, which is the minimum number needed.
Village 5: we can traverse the 5-th waterway to go to Village 3, and then traverse the 2-nd waterway to go to Village 1, which is a place of refuge. We have traversed 2 waterway, which is the minimum number needed.

Sample Input 2

Sample Output 2

From Village 5, we cannot go to any other village. It is not a place of refuge itself, either, so the 5-th line should contain -1.

Sample Input 3

Sample Output 3

J - Long Long String

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

問題文

以下のようなプログラミング言語があります。
プログラムは命令を表す文字の列であり、前から順に実行されます。各文字が表す命令の意味は下の通りです。

英小文字 c : c を出力する
数字 x : プログラムの先頭から、現在実行中の命令の一つ前の命令までの命令列を、もう x 回実行する

例えば、プログラム ab2c1 は文字列 abababcabababc を出力します。

プログラム S が与えられます。S が出力する文字列の X 番目の文字を求めてください。

制約

1 \le |S| \le 2 \times 10^5
S は英小文字及び 1 以上 9 以下の数字からなる
1 \le X \le 10^{15}
S は X 文字以上出力する

入力

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

S
X

出力

S が出力する文字列の X 番目の文字を出力せよ。

入力例 1

ab2c1
6

出力例 1

プログラム ab2c1 は以下のように動作し、文字列 abababcabababc を出力します。

最初の 2 文字が実行されて、ab が出力される
3 文字目に 2 があるので、S の最初の 2 文字がもう 2 回実行され、abab が出力される
4 文字目が実行され、c が出力される
5 文字目に 1 があるので、上の 3 行がもう一度繰り返され、abababc が出力される

出力される文字列は最終的に abababcabababc であり、この 6 文字目は b です。

入力例 2

atcoder
6

出力例 2

S に数字が含まれていないので、そのまま atcoder が出力されます。

入力例 3

a999999999999999
1000000000000000

出力例 3

S が出力する文字数は非常に大きくなることがあることに注意してください。

Score : 6 points

Warning

Problem Statement

Consider the following programming language:

A program is a sequence of characters, each representing an instruction, executed from left to right. Each character represents the following instruction:

A lowercase English letter c: print c.
A digit x: Execute the following x more times: the subsequence of instructions from the beginning of the program through the instruction immediately before the current instruction.

For example, the program ab2c1 prints the string abababcabababc.

Given a program S, find the X-th character of the string printed by S.

Constraints

1 \le |S| \le 2 \times 10^5
S consists of lowercase English letters and digits from 1 through 9.
1 \le X \le 10^{15}
S prints at least X characters.

Input

Input is given from Standard Input in the following format:

S
X

Output

Print the X-th character of the string printed by S.

Sample Input 1

ab2c1
6

Sample Output 1

The program ab2c1 runs as follows and prints the string abababcabababc.

The first two characters print ab.
The third character 2 executes the first two characters two more times and prints abab.
The fourth character prints c.
The fifth character 1 performs the process described by the above three lines and prints abababc.

In the end, the program prints the string abababcabababc, whose 6-th character is b.

Sample Input 2

atcoder
6

Sample Output 2

S contains no digit, so it just prints atcoder.

Sample Input 3

a999999999999999
1000000000000000

Sample Output 3

Note that S can print extremely many characters.

K - Pitching

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

問題文

あなたは 4 \times 4 のグリッドを使って的あてゲームをしています。

グリッドの上から i 行目、左から j 列目のマスには、S_{i,j} が . のとき的はなく、# のとき的があります。全ての的に 1 度以上ボールを当てるとゲームクリアです。

あなたがあるマスを狙ってボールを投げると、狙ったマスか 1 マス分上下左右にズレた場所(グリッド外も含む)にそれぞれ \dfrac{1}{5} の確率で飛んでいき、そこに的があれば当たります。

ゲームの進行に伴い狙うマスを適切に選択するとき、ゲームをクリアするまでにボールを投げる回数の期待値は最小でいくらになりますか？

制約

S_{i,j} は . または #
S_{i,j} のうち少なくとも 1 個は # である

入力

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

S_{1,1}S_{1,2}S_{1,3}S_{1,4}
S_{2,1}S_{2,2}S_{2,3}S_{2,4}
S_{3,1}S_{3,2}S_{3,3}S_{3,4}
S_{4,1}S_{4,2}S_{4,3}S_{4,4}

出力

ボールを投げる回数の期待値の最小値を出力せよ。

正しい値との絶対誤差または相対誤差が 10^{-6} 以下であれば正解とみなされる。

入力例 1

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

出力例 1

5.0000000000

的にボールが当たるまでの回数の期待値は 5 です。グリッドの外へボールが飛んでいくこともあります。

入力例 2

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

出力例 2

7.5000000000

2 つある的のどちらかにボールが当たるまでは、上の的を狙います。一方の的に当たったあとは、残りの的を狙います。

入力例 3

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

出力例 3

10.4166666667

最初のうちは 4 つの的の中央にある、的のないマスを狙うのが最適です。

入力例 4

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

出力例 4

32.5674089515

Score : 6 points

Warning

Problem Statement

You are playing the game "Hit the Targets" with a 4 \times 4 grid.

The square at the i-th row from the top and j-th column from the left contains a target if S_{i, j} is #, and it does not if S_{i, j} is .. You win the game when you hit every target with a ball once or more.

When you throw a ball aiming at some square x, the ball flies to one of the following five squares, each with probability \dfrac{1}{5}: x itself and the four squares vertically or horizontally adjacent to x. (Assume that there are empty squares outside the grid.) If that square contains a target, the ball hits it.

What is the expected value of the number of throws before winning the game, assuming that you always make the optimal choice to minimize this value during the game?

Constraints

S_{i,j} is . or #.
At least one of the characters S_{i,j} is #.

Input

Input is given from Standard Input in the following format:

S_{1,1}S_{1,2}S_{1,3}S_{1,4}
S_{2,1}S_{2,2}S_{2,3}S_{2,4}
S_{3,1}S_{3,2}S_{3,3}S_{3,4}
S_{4,1}S_{4,2}S_{4,3}S_{4,4}

Output

Print the minimized expected value of the number of throws.

Your output will be accepted if its absolute or relative error from the correct answer is at most 10^{-6}.

Sample Input 1

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

Sample Output 1

5.0000000000

The expected number of throws before hitting the target is 5. Note that balls can miss the grid.

Sample Input 2

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

Sample Output 2

7.5000000000

Until a ball hits one of the two targets, we will aim at the upper target, and then we will aim at the remaining target.

Sample Input 3

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

Sample Output 3

10.4166666667

In the beginning, it is optimal to aim at the empty square at the center of the four targets.

Sample Input 4

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

Sample Output 4

32.5674089515

L - Collecting T

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

問題文

長さ N の文字列 S と、長さ 3 の文字列 T が与えられます。
あなたは以下の操作を繰り返すことができます。

S の中の連続する 3 文字であって T と一致するものを選び、その 3 文字を S から消す (消した後、残っている文字は連結される)

最大で何回操作することができますか？

制約

1 \le N \le 100
S は英小文字からなる長さ N の文字列
T は英小文字からなる長さ 3 の文字列

入力

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

N
S
T

出力

最大の操作回数を出力せよ。

入力例 1

7
adbabcd
abc

出力例 1

S の 4 文字目から 6 文字目までが T に一致するのでこれを消すことができます。
これ以上操作することはできないので、答えは 1 です。

入力例 2

6
ababaa
aba

出力例 2

まず、S の 3 文字目から 5 文字目までが T に一致するので、これを消すことができます。
S は aba となったので、S の全体が T に一致し、もう一度操作ができます。
よって、答えは 2 です。

入力例 3

6
zzzzzz
abc

出力例 3

全く操作できない可能性もあります。

Score : 6 points

Warning

Problem Statement

Given are a string S of length N and a string T of length 3.
You can repeatedly do the following operation:

Choose three consecutive characters in S that coincide with T and remove those characters from S. (The remaining parts get concatenated.)

What is the maximum number of operations that can be done?

Constraints

1 \le N \le 100
S is a string of length N consisting of lowercase English letters.
T is a string of length 3 consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S
T

Output

Print the maximum number of operations that can be done.

Sample Input 1

7
adbabcd
abc

Sample Output 1

The 4-th through 6-th characters of S coincide with T, so we can erase them.
We cannot do anything more, so the answer is 1.

Sample Input 2

6
ababaa
aba

Sample Output 2

First, the 3-rd through 5-th characters of S coincide with T, so we can erase them.
S becomes aba, which coincides with T and can be erased again.
Thus, the answer is 2.

Sample Input 3

6
zzzzzz
abc

Sample Output 3

Sometimes, we can do nothing.

M - Shipping Sticks

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

問題文

左右に横たわる細長い棒に N - 1 箇所の切れ込みがあります。この棒を全ての切れ込みで切断すると、左から順に長さ A_1, A_2, A_3, \dots, A_N の N 本の棒に分かれます。
あなたは、N - 1 箇所の切れ込みのうちいくつかを選び、選んだ箇所でこの棒を切断してから出荷します。(1 箇所も選ばなくても、全部選んでも構いません。)
あまり長い棒は扱いに困るので、切断後に全ての棒の長さが L 以下になるように切ります。また、棒の長さに偏りが生じないように、切断後の一番短い棒の長さをできる限り長くします。
切断後の一番短い棒の長さとして考えられる最大値を求めてください。

制約

1 \le N \le 2 \times 10^5
1 \le L \le 10^{15}
1 \le A_i \le \min(10^9, L)
入力は全て整数

入力

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

N L
A_1 A_2 A_3 \dots A_N

出力

切断後の一番短い棒の長さとして考えられる最大値を出力せよ。

入力例 1

5 10
3 4 1 2 4

出力例 1

左から 2 番目の切れ込みだけで切断すると、出来上がる 2 つの棒の長さはそれぞれ 3 + 4 = 7, 1 + 2 + 4 = 7 となり、一番短い棒の長さは 7 となります。
これが最大です。　　

入力例 2

8 10
7 2 1 5 3 2 5 2

出力例 2

左から 2, 5 番目の切れ込みで切断すると、長さ 9 の棒が 3 本出来上がります。

入力例 3

13 10000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

6000000000

長さ 6000000000 の棒と、長さ 7000000000 の棒が一つずつできるような切り方が最適です。

Score : 6 points

Warning

Problem Statement

We have a long and narrow stick with N - 1 notches, lying from left to right. Cutting this stick at all of the notches will separate this stick into N sticks of length A_1, A_2, A_3, \dots, A_N from left to right.
You will choose some of the notches (possibly none or all), cut the stick at the chosen notches, and ship the resulting sticks.
Too long sticks are troublesome, so you will make the cuts so that the length of every resulting stick is at most L. Also, to make the lengths of the resulting sticks as uniform as possible, you will maximize the length of the shortest resulting stick.
Find the maximum possible length of the shortest resulting stick.

Constraints

1 \le N \le 2 \times 10^5
1 \le L \le 10^{15}
1 \le A_i \le \min(10^9, L)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N L
A_1 A_2 A_3 \dots A_N

Output

Print the maximum possible length of the shortest resulting stick.

Sample Input 1

5 10
3 4 1 2 4

Sample Output 1

Cutting the stick at just the 2-nd notch from the left results in two sticks of length 3 + 4 = 7 and 1 + 2 + 4 = 7, the minimum of which is 7.
This is the maximum possible result.

Sample Input 2

8 10
7 2 1 5 3 2 5 2

Sample Output 2

Cutting the stick at the 2-nd and 5-th notches from the left results in three sticks of length 9 each.

Sample Input 3

13 10000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

6000000000

It is optimal to make two sticks of lengths 6000000000 and 7000000000.

N - Travel Agency

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

問題文

ある国には N 個の都市があり、都市 1 から都市 N と番号付けされています。
この国には N - 1 本の道路がありますが、道路はどれも危険なため年齢制限が設定されています。 i 番目の道路は都市 i と都市 i + 1 を双方向に結び、L_i 才以上 R_i 才以下の人が通行可能です。
あなたはこの国で旅行会社を立ち上げました。客からの Q 個の質問に答えてください。
i 個目の質問では A_i, B_i が与えられるので、A_i 才の人が都市 B_i から旅行を始めるとき、道路を辿って訪れることが可能な都市 (都市 B_i 自身を含む) の数を求めてください。旅行中この人の年齢は変わらないものとします。

制約

1 \le N \le 2 \times 10^5
1 \le Q \le 2 \times 10^5
1 \le L_i \le R_i \le 10^9
1 \le A_i \le 10^9
1 \le B_i \le N
入力は全て整数

入力

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

N Q
L_1 R_1
L_2 R_2
L_3 R_3
\hspace{15pt} \vdots
L_{N - 1} R_{N - 1}
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_Q B_Q

出力

Q 行に渡って、i 行目には i 番目の質問に対する答えを出力せよ。

入力例 1

出力例 1

3
3
2

1 個目の質問では、3 才の人が都市 1 から旅行を始めます。3 番目の道路以外は通れるので、到達可能なのは都市 1 から都市 3 までの 3 個です。
2 個目の質問では、2 才の人が都市 2 から旅行を始めます。1 番目の道路以外は通れるので、到達可能なのは都市 2 から都市 4 までの 3 個です。
3 個目の質問では、1 才の人が都市 4 から旅行を始めます。通れるのは 3 番目の道路だけなので、到達可能なのは都市 3 と都市 4 の 2 個です。

入力例 2

出力例 2

5
3
1

Score : 6 points

Warning

Problem Statement

In a country, there are N cities, numbered 1 through N.
The country has N - 1 roads, which are full of dangers. Thus, for each road, only people whose ages are within a certain range are permitted to traverse it; the i-th road connects City i and City i + 1 bidirectionally, and only people between the ages of L_i and R_i can traverse it.
You have started a travel agency in this country. Respond to Q queries from customers.
In the i-th query, given values A_i and B_i, find the number of cities that an A_i-year-old person can reach by starting at City B_i and traversing roads. (City B_i is also considered reachable.) We assume that the person does not get older during the trip.

Constraints

1 \le N \le 2 \times 10^5
1 \le Q \le 2 \times 10^5
1 \le L_i \le R_i \le 10^9
1 \le A_i \le 10^9
1 \le B_i \le N
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
L_1 R_1
L_2 R_2
L_3 R_3
\hspace{15pt} \vdots
L_{N - 1} R_{N - 1}
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_Q B_Q

Output

Print Q lines. The i-th line should contain the response to the i-th query.

Sample Input 1

Sample Output 1

3
3
2

In the first query, a 3-year-old starts at City 1. The roads except the 3-rd one are passable, so the person can reach three cities: City 1 through 3.
In the second query, a 2-year-old starts at City 2. The roads except the 1-st one are passable, so the person can reach three cities: City 2 through 4.
In the third query, a 1-year-old starts at City 4. Only the third road is passable, so the person can reach two cities: City 3 and 4.

Sample Input 2

Sample Output 2

5
3
1

O - Notification

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

問題文

あなたは、N 人のユーザが利用する SNS を運営しています。ユーザは 1 から N まで番号付けられていて、ユーザは他のユーザと双方向の友達関係を作ることができます。
今、この SNS には M 対の友達関係が成立しています。友達関係にも 1 から M までの番号がつけられており、i 番目の友達関係はユーザ a_i とユーザ b_i の間の関係です。

あなたの仕事は、この SNS に新たな機能を追加することです。
Q 個のクエリが与えられるので、順番に処理してください。 i 番目のクエリでは、整数 T_i, x_i が与えられます。クエリの内容は以下の通りです。

T_i = 1 のとき : ユーザ x_i と直接友達関係を持つユーザ全員 (ユーザ x_i は除く) に通知を 1 件送信する。これらの通知は最初未読の状態である。
T_i = 2 のとき : これまでにユーザ x_i に送信された通知のうち、未読のものの数を出力する。その後、それらの通知を既読にする。

制約

入力は全て整数
2 \le N \le 2 \times 10^5
1 \le M \le 2 \times 10^5
1 \le a_i \lt b_i \le N
i \neq j ならば (a_i, b_i) \neq (a_j, b_j)
1 \le Q \le 2 \times 10^5
T_i \in \{1, 2\}
1 \le x_i \le N

入力

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

N M
a_1 b_1
\vdots
a_M b_M
Q
T_1 x_1
\vdots
T_Q x_Q

出力

T_i = 2 のクエリごとに、答えを 1 行に出力せよ。

入力例 1

出力例 1

1
2
0

1 回目のクエリでは、ユーザ 1 の直接の友達である、ユーザ 2,3 に通知を 1 件送信します。各ユーザの未読通知の数は 0,1,1 になります。
2 回目のクエリでは、ユーザ 2 の未読通知の数である 1 を出力します。各ユーザの未読通知の数は 0,0,1 になります。
3 回目のクエリでは、ユーザ 1 の直接の友達である、ユーザ 2,3 に通知を 1 件送信します。各ユーザの未読通知の数は 0,1,2 になります。
4 回目のクエリでは、ユーザ 3 の未読通知の数である 2 を出力します。各ユーザの未読通知の数は 0,1,0 になります。
5 回目のクエリでは、ユーザ 1 の未読通知の数である 0 を出力します。各ユーザの未読通知の数は 0,1,0 になります。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 6 points

Warning

Problem Statement

You run a social networking service used by N users. The users, numbered 1 through N, can make bidirectional friendships with other users.
There are now M friendships in the service, numbered 1 through M; Friendship i is between User a_i and User b_i.

Your task is to add new features to the service.
Process Q queries in the order they are given. The i-th query gives you integers T_i and x_i, which mean the following:

If T_i = 1: a notification is sent to each user (excluding User x_i) who is a direct friend of User x_i. These notifications are initially unread.
If T_i = 2: print the number of unread notifications sent to User x_i. Then, those notifications are marked as read.

Constraints

All values in input are integers.
2 \le N \le 2 \times 10^5
1 \le M \le 2 \times 10^5
1 \le a_i \lt b_i \le N
If i \neq j, then (a_i, b_i) \neq (a_j, b_j).
1 \le Q \le 2 \times 10^5
T_i \in \{1, 2\}
1 \le x_i \le N

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
\vdots
a_M b_M
Q
T_1 x_1
\vdots
T_Q x_Q

Output

For each query with T_i = 2, print the response in its own line.

Sample Input 1

Sample Output 1

1
2
0

In the first query, a notification is sent to the direct friends of User 1 - User 2 and 3. Now, User 1, 2, 3 has 0, 1, 1 unread notification(s), respectively.
In the second query, we print the number of unread notifications sent to User 2, which is 1. Now, User 1, 2, and 3 has 0, 0, and 1 unread notification(s), respectively.
In the third query, a notification is sent to the direct friends of User 1 - User 2 and 3. Now, User 1, 2, 3 has 0, 1, 2 unread notification(s), respectively.
In the fourth query, we print the number of unread notifications sent to User 3, which is 2. Now, User 1, 2, 3 has 0, 1, 0 unread notification(s), respectively.
In the fifth query, we print the number of unread notifications sent to User 1, which is 0. Now, User 1, 2, 3 has 0, 1, 0 unread notification(s), respectively.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3