A - Shift

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

配点 : 100 点

問題文

長さ N の数列 A = (A_1, A_2, \dots, A_N) が与えられます。
あなたは次の操作をちょうど K 回行います。

  • A の先頭の要素を取り除き、A の末尾に 0 を挿入する。

操作を行った後の A の要素をすべて出力してください。

制約

  • 1 \leq N \leq 100
  • 1 \leq K \leq 100
  • 1 \leq A_i \leq 100
  • 入力される値はすべて整数

入力

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

N K
A_1 A_2 \dots A_N

出力

操作を行った後の A の要素を空白区切りで 1 行に出力せよ。


入力例 1

3 2
2 7 8

出力例 1

8 0 0

操作を行う前は A = (2, 7, 8) です。
操作を 1 回行った時点では A = (7, 8, 0) です。
操作を 2 回行った時点では A = (8, 0, 0) です。
よって (8, 0, 0) が答えです。


入力例 2

3 4
9 9 9

出力例 2

0 0 0

入力例 3

9 5
1 2 3 4 5 6 7 8 9

出力例 3

6 7 8 9 0 0 0 0 0

Score : 100 points

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N.
You perform the following operation exactly K times:

  • remove the initial element of A and append a 0 to the tail of A.

Print all the elements of A after the operations.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq K \leq 100
  • 1 \leq A_i \leq 100
  • All values in the input are integers.

Input

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

N K
A_1 A_2 \dots A_N

Output

Print the elements of A after the operations in one line, separated by spaces.


Sample Input 1

3 2
2 7 8

Sample Output 1

8 0 0

Before the operations, A = (2, 7, 8).
After performing the operation once, A = (7, 8, 0).
After performing the operation twice, A = (8, 0, 0).
Thus, (8, 0, 0) is the answer.


Sample Input 2

3 4
9 9 9

Sample Output 2

0 0 0

Sample Input 3

9 5
1 2 3 4 5 6 7 8 9

Sample Output 3

6 7 8 9 0 0 0 0 0
B - Weird Function

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

配点 : 100 点

問題文

関数 f を f(x) = x^2 + 2x + 3 と定義します。
整数 t が入力されるので、 f(f(f(t)+t)+f(f(t))) を求めてください。
ただし、答えは 2 \times 10^9 以下の整数であることが保証されます。

制約

  • t は 0 以上 10 以下の整数である

入力

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

t

出力

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


入力例 1

0

出力例 1

1371

答えは以下の手順によって計算されます。

  • f(t) = t^2 + 2t + 3 = 0 \times 0 + 2 \times 0 + 3 = 3
  • f(t)+t = 3 + 0 = 3
  • f(f(t)+t) = f(3) = 3 \times 3 + 2 \times 3 + 3 = 18
  • f(f(t)) = f(3) = 18
  • f(f(f(t)+t)+f(f(t))) = f(18+18) = f(36) = 36 \times 36 + 2 \times 36 + 3 = 1371

入力例 2

3

出力例 2

722502

入力例 3

10

出力例 3

1111355571

Score : 100 points

Problem Statement

Let us define a function f as f(x) = x^2 + 2x + 3.
Given an integer t, find f(f(f(t)+t)+f(f(t))).
Here, it is guaranteed that the answer is an integer not greater than 2 \times 10^9.

Constraints

  • t is an integer between 0 and 10 (inclusive).

Input

Input is given from Standard Input in the following format:

t

Output

Print the answer as an integer.


Sample Input 1

0

Sample Output 1

1371

The answer is computed as follows.

  • f(t) = t^2 + 2t + 3 = 0 \times 0 + 2 \times 0 + 3 = 3
  • f(t)+t = 3 + 0 = 3
  • f(f(t)+t) = f(3) = 3 \times 3 + 2 \times 3 + 3 = 18
  • f(f(t)) = f(3) = 18
  • f(f(f(t)+t)+f(f(t))) = f(18+18) = f(36) = 36 \times 36 + 2 \times 36 + 3 = 1371

Sample Input 2

3

Sample Output 2

722502

Sample Input 3

10

Sample Output 3

1111355571
C - Distance Table

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

配点 : 200 点

問題文

N 個の駅、駅 1, 駅 2, \ldots, 駅 N が直線上にこの順に並んでいます。
ここで、1\leq i\leq N-1 について、駅 i と駅 (i+1) の間の距離は D_i です。

1\leq i<j\leq N をみたす整数の組 (i,j) それぞれについて、駅 i と駅 j の間の距離を求めてください。
なお、出力形式については出力の欄を参照してください。

制約

  • 2 \leq N \leq 50
  • 1 \leq D_i \leq 100
  • 入力はすべて整数

入力

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

N
D_1 D_2 \ldots D_{N-1}

出力

N-1 行出力せよ。
i 行目 (1\leq i\leq N-1) には、(N-i) 個の整数を空白区切りで出力せよ。
i 行目の j 番目 (1\leq j\leq N-i) には、駅 i と駅 (i+j) の間の距離を出力せよ。


入力例 1

5
5 10 2 3

出力例 1

5 15 17 20
10 12 15
2 5
3

各駅の間の距離は次のようになります。

  • 駅 1 と駅 2 の間の距離は 5 です。
  • 駅 1 と駅 3 の間の距離は 5+10=15 です。
  • 駅 1 と駅 4 の間の距離は 5+10+2=17 です。
  • 駅 1 と駅 5 の間の距離は 5+10+2+3=20 です。
  • 駅 2 と駅 3 の間の距離は 10 です。
  • 駅 2 と駅 4 の間の距離は 10+2=12 です。
  • 駅 2 と駅 5 の間の距離は 10+2+3=15 です。
  • 駅 3 と駅 4 の間の距離は 2 です。
  • 駅 3 と駅 5 の間の距離は 2+3=5 です。
  • 駅 4 と駅 5 の間の距離は 3 です。

よって、上記のように出力します。


入力例 2

2
100

出力例 2

100

Score : 200 points

Problem Statement

There are N stations, station 1, station 2, \ldots, station N, arranged in this order on a straight line.
Here, for 1\leq i\leq N-1, the distance between stations i and (i+1) is D_i.

For each pair of integers (i,j) satisfying 1\leq i<j\leq N, find the distance between stations i and j.
For the output format, refer to the Output section.

Constraints

  • 2 \leq N \leq 50
  • 1 \leq D_i \leq 100
  • All input values are integers.

Input

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

N
D_1 D_2 \ldots D_{N-1}

Output

Output N-1 lines.
On the i-th line (1\leq i\leq N-1), output (N-i) integers, separated by spaces.
The j-th integer on the i-th line (1\leq j\leq N-i) should be the distance between stations i and (i+j).


Sample Input 1

5
5 10 2 3

Sample Output 1

5 15 17 20
10 12 15
2 5
3

The distances between stations are as follows:

  • The distance between stations 1 and 2 is 5.
  • The distance between stations 1 and 3 is 5+10=15.
  • The distance between stations 1 and 4 is 5+10+2=17.
  • The distance between stations 1 and 5 is 5+10+2+3=20.
  • The distance between stations 2 and 3 is 10.
  • The distance between stations 2 and 4 is 10+2=12.
  • The distance between stations 2 and 5 is 10+2+3=15.
  • The distance between stations 3 and 4 is 2.
  • The distance between stations 3 and 5 is 2+3=5.
  • The distance between stations 4 and 5 is 3.

Thus, output as shown above.


Sample Input 2

2
100

Sample Output 2

100
D - Ticket Gate Log

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

配点 : 250 点

問題文

高橋君は改札機の利用履歴を集計しました。 しかし、高橋君はうっかりいくつかの入退場記録を消してしまいました。 高橋君は消してしまった記録の復元を試みようとしています。

i, o のみからなる文字列 S が与えられます。 S の任意の位置に文字を 0 文字以上挿入することで、変更後の文字列が以下の条件を満たすようにしたいです。

  • 長さが偶数であり、奇数文字目が i で偶数文字目が o である。

挿入する必要のある文字数の最小値を求めて下さい。なお、問題の制約下で、有限個の文字を適切に挿入することで、S が条件をみたすようにできることが証明できます。

制約

  • S は i, o からなる長さ 1 以上 100 以下の文字列

入力

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

S

出力

答えを出力せよ。


入力例 1

ioi

出力例 1

1

3 文字目のあとに o を挿入して ioio とすることで、条件を満たすことができます。0 文字以下の挿入で条件を満たすことはできません。


入力例 2

iioo

出力例 2

2

1 文字目のあとに o を、3 文字目のあとに i を挿入することで、条件を満たすことができます。1 文字以下の挿入で条件を満たすことはできません。


入力例 3

io

出力例 3

0

S がすでに条件を満たします。

Score : 250 points

Problem Statement

Takahashi aggregated usage records from ticket gates. However, he accidentally erased some records of entering and exiting stations. He is trying to restore the erased records.

You are given a string S consisting of i and o. We want to insert zero or more characters at arbitrary positions in S so that the resulting string satisfies the following conditions:

  • Its length is even, and every odd-numbered (1st, 3rd, ...) character is i while every even-numbered (2nd, 4th, ...) character is o.

Find the minimum number of characters that need to be inserted. It can be proved under the constraints of this problem that by inserting an appropriate finite number of characters, S can be made to satisfy the conditions.

Constraints

  • S is a string of length between 1 and 100, consisting of i and o.

Input

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

S

Output

Print the answer.


Sample Input 1

ioi

Sample Output 1

1

We can insert o after the 3rd character to form ioio to satisfy the conditions. The conditions cannot be satisfied by inserting zero or fewer characters.


Sample Input 2

iioo

Sample Output 2

2

We can insert o after the 1st character and i after the 3rd character to satisfy the conditions. The conditions cannot be satisfied by inserting one or fewer characters.


Sample Input 3

io

Sample Output 3

0

S already satisfies the conditions.

E - Bipartize

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



配点 : 350 点

問題文

N 頂点 M 辺の単純な無向グラフがあります。 グラフは頂点 1, 頂点 2,\ldots, 頂点 N からなり、i 番目 (1\le i\le M) の辺は頂点 u _ i と頂点 v _ i を結んでいます。

あなたは、次の操作を 0 回以上行います。

  • まだ削除されていない辺をひとつ選び、削除する。

あなたの目的はグラフを二部グラフにすることです。 操作を行ったあとのグラフを二部グラフにするために、最低でも何回操作を行う必要があるか求めてください。

グラフが単純であるとは

グラフが単純であるとは、自己ループ(u _ i=v _ i となる辺)や多重辺(u _ i=u _ j かつ v _ i=v _ j となる辺のペア)が存在しないことをいいます。

二部グラフとは

二部グラフとは、頂点をそれぞれ黒か白のどちらか一色で塗り、次の条件を満たすことができるグラフのことをいいます。

  • どの辺についても、その辺が結んでいるふたつの頂点に塗られた色は異なる。

制約

  • 2\le N\le10
  • 1\le M\le\dfrac{N(N-1)}2
  • 1\le u _ i\lt v _ i\le N\ (1\le i\le M)
  • 与えられるグラフは単純
  • 入力はすべて整数

入力

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

N M
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ M v _ M

出力

操作を行ったあとのグラフを二部グラフにするために、行う必要がある操作の回数を出力せよ。


入力例 1

5 8
1 2
1 3
1 4
2 3
2 5
3 4
3 5
4 5

出力例 1

2

例えば、頂点 1 と頂点 3 を結ぶ辺、頂点 3 と頂点 5 を結ぶ辺の 2 つを削除することでグラフを二部グラフにすることができます。

操作を 1 回以下行うことでグラフを二部グラフにすることはできないため、2 を出力してください。


入力例 2

2 1
1 2

出力例 2

0

グラフははじめから二部グラフです。 よって、行う必要がある操作の回数は 0 回です。


入力例 3

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

出力例 3

5

Score : 350 points

Problem Statement

There is a simple undirected graph with N vertices and M edges. The graph consists of vertex 1, vertex 2,\ldots, vertex N, and the i-th edge (1\le i\le M) connects vertices u _ i and v _ i.

You will perform the following operation zero or more times:

  • Choose one edge that has not been deleted yet, and delete it.

Your goal is to make the graph bipartite. Find the minimum number of operations needed to make the graph after the operations bipartite.

What it means for a graph to be simple?

A graph is simple if and only if it has no self-loops (edges where u _ i=v _ i) or multi-edges (pairs of edges where u _ i=u _ j and v _ i=v _ j).

What is a bipartite graph?

A bipartite graph is a graph where it is possible to color each vertex black or white satisfying the following condition:

  • For every edge, the two vertices connected by that edge have different colors.

Constraints

  • 2\le N\le10
  • 1\le M\le\dfrac{N(N-1)}2
  • 1\le u _ i\lt v _ i\le N\ (1\le i\le M)
  • The given graph is simple.
  • All input values are integers.

Input

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

N M
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ M v _ M

Output

Print the number of operations that need to be performed to make the graph bipartite.


Sample Input 1

5 8
1 2
1 3
1 4
2 3
2 5
3 4
3 5
4 5

Sample Output 1

2

You can make the graph bipartite by deleting two edges: for example, the edge connecting vertices 1 and 3, and the edge connecting vertices 3 and 5.

It is impossible to make the graph bipartite by performing one or less operations, so print 2.


Sample Input 2

2 1
1 2

Sample Output 2

0

The graph is bipartite from the beginning. Thus, the number of operations that need to be performed is 0.


Sample Input 3

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

Sample Output 3

5
F - String Delimiter

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

配点 : 300 点

問題文

英小文字、,、" からなる長さ N の文字列 S が与えられます。S に含まれる " の個数は偶数であることが保証されています。

S に含まれる " の個数を 2K 個とすると、各 i=1,2,\ldots,K について 2i-1 番目の " から 2i 番目の " までの文字のことを 括られた文字 と呼びます。

あなたの仕事は、 S に含まれる , のうち、括られた文字 でないもの を . で置き換えて得られる文字列を答えることです。

制約

  • N は 1 以上 2\times 10^5 以下の整数
  • S は英小文字、,、" からなる長さ N の文字列
  • S に含まれる " の個数は偶数

入力

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

N
S

出力

答えを出力せよ。


入力例 1

8
"a,b"c,d

出力例 1

"a,b"c.d

S のうち "a,b" が括られた文字であり、c,d は括られた文字ではありません。

S に含まれる , のうち、括られた文字でないのは S の左から 7 番目の文字なので、7 番目の文字を . で置き換えたものが答えとなります。


入力例 2

5
,,,,,

出力例 2

.....

入力例 3

20
a,"t,"c,"o,"d,"e,"r,

出力例 3

a."t,"c."o,"d."e,"r.

Score : 300 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters, ,, and ". It is guaranteed that S contains an even number of ".

Let 2K be the number of " in S. For each i=1,2,\ldots,K, the characters from the (2i-1)-th " through the (2i)-th " are said to be enclosed.

Your task is to replace each , in S that is not an enclosed character with . and print the resulting string.

Constraints

  • N is an integer between 1 and 2\times 10^5, inclusive.
  • S is a string of length N consisting of lowercase English letters, ,, and ".
  • S contains an even number of ".

Input

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

N
S

Output

Print the answer.


Sample Input 1

8
"a,b"c,d

Sample Output 1

"a,b"c.d

In S, "a,b" are enclosed characters, and c,d are not.

The , in S that is not an enclosed character is the seventh character from the left in S, so replace that character with . to get the answer.


Sample Input 2

5
,,,,,

Sample Output 2

.....

Sample Input 3

20
a,"t,"c,"o,"d,"e,"r,

Sample Output 3

a."t,"c."o,"d."e,"r.
G - Money in Hand

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

配点 : 400 点

問題文

高橋君は N 種類の硬貨をそれぞれ何枚か持っており、 具体的には、1\leq i\leq N について A_i 円硬貨を B_i 枚持っています。

高橋君が現在持っている硬貨を用いて、(お釣りが出ないように)ちょうど X 円を支払うことができるか判定してください。

制約

  • 1\leq N\leq 50
  • 1\leq X\leq 10^4
  • 1\leq A_i\leq 100
  • 1\leq B_i\leq 50
  • A_i はすべて異なる。
  • 入力はすべて整数

入力

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

N X
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

高橋君が現在持っている硬貨を用いてちょうど X 円を支払うことができる場合は Yes を、 できない場合は No を出力せよ。


入力例 1

2 19
2 3
5 6

出力例 1

Yes

高橋君は 2 円硬貨を 3 枚、5 円硬貨を 6 枚持っています。 このうち、2 円硬貨を 2 枚、5 円硬貨を 3 枚用いることでちょうど 2\times 2+5\times 3=19 円を支払うことができます。 よって、Yes を出力します。


入力例 2

2 18
2 3
5 6

出力例 2

No

持っている硬貨をどのように組み合わせてもちょうど 18 円を支払うことはできません。 よって、No を出力します。


入力例 3

3 1001
1 1
2 1
100 10

出力例 3

Yes

1 枚も使用しない硬貨が存在しても構いません。

Score : 400 points

Problem Statement

Takahashi has N kinds of coins; specifically, for 1\leq i\leq N, he has B_i coins worth A_i yen (the currency in Japan) each.

Determine if Takahashi can pay exactly X yen (without change) with the coins he currently has.

Constraints

  • 1\leq N\leq 50
  • 1\leq X\leq 10^4
  • 1\leq A_i\leq 100
  • 1\leq B_i\leq 50
  • A_i are pairwise distinct.
  • All values in the input are integers.

Input

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

N X
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print Yes if Takahashi can pay exactly X yen with the coins he currently has; print No otherwise.


Sample Input 1

2 19
2 3
5 6

Sample Output 1

Yes

Takahashi has three 2-yen coins and six 5-yen coins. He can use two 2-yen coins and three 5-yen coins to pay exactly 2\times 2+5\times 3=19 yen. Thus, Yes should be printed.


Sample Input 2

2 18
2 3
5 6

Sample Output 2

No

There is no combination of the coins that he can use to pay exactly 18 yen. Thus, No should be printed.


Sample Input 3

3 1001
1 1
2 1
100 10

Sample Output 3

Yes

He need not use all kinds of coins.

H - A > B substring

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

配点 : 450 点

問題文

A, B, C の 3 種類の文字からなる長さ N の文字列 S が与えられます。

S の空でない連続する部分文字列は \dfrac{N(N+1)}2 個ありますが、そのうち A が B よりも多く含まれるものはいくつあるか求めてください。

2 つの部分文字列は、S から取り出す場所が異なれば文字列として等しくても区別して数えることに注意してください。

部分文字列とは

S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。
例えば、AB は ABC の部分文字列ですが、AC は ABC の部分文字列ではありません。

制約

  • 1\le N\le5\times10 ^ 5
  • S は A, B, C からなる長さ N の文字列
  • N は整数

入力

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

N
S

出力

S の連続する部分文字列のうち A が B よりも多く含まれるものの個数を出力せよ。


入力例 1

10
ACBBCABCAB

出力例 1

8

以下の 8 つの部分文字列が条件を満たします。

  • A:S の 1 文字目から 1 文字目
  • AC:S の 1 文字目から 2 文字目
  • CA:S の 5 文字目から 6 文字目
  • CABCA:S の 5 文字目から 9 文字目
  • A:S の 6 文字目から 6 文字目
  • ABCA:S の 6 文字目から 9 文字目
  • CA:S の 8 文字目から 9 文字目
  • A:S の 9 文字目から 9 文字目

これら以外の部分文字列は条件を満たさないため、8 を出力してください。

A や CA は複数箇所から取り出すことができますが、取り出す場所が異なれば区別して数えることに注意してください。


入力例 2

4
CCBC

出力例 2

0

条件を満たす部分文字列が存在しないこともあります。


入力例 3

36
CABACBBBBBAABABACCBCABCCABAABABBCBAC

出力例 3

136

Score : 450 points

Problem Statement

You are given a string S of length N consisting of three kinds of characters: A, B, and C.

There are \dfrac{N(N+1)}2 non-empty contiguous substrings of S. Find how many of them contain more As than Bs.

Note that two substrings are counted separately if they are taken from different positions in S, even if they are equal as strings.

What is a substring?

A substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, AB is a substring of ABC, but AC is not a substring of ABC.

Constraints

  • 1\le N\le5\times10 ^ 5
  • S is a string of length N consisting of A, B, and C.
  • N is an integer.

Input

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

N
S

Output

Print the number of contiguous substrings of S that contain more As than Bs.


Sample Input 1

10
ACBBCABCAB

Sample Output 1

8

The following eight substrings satisfy the condition:

  • A: 1st to 1st character of S
  • AC: 1st to 2nd character of S
  • CA: 5th to 6th character of S
  • CABCA: 5th to 9th character of S
  • A: 6th to 6th character of S
  • ABCA: 6th to 9th character of S
  • CA: 8th to 9th character of S
  • A: 9th to 9th character of S

All other substrings do not satisfy the condition, so print 8.

Note that A and CA can be taken from multiple positions, but they are counted separately if taken from different positions.


Sample Input 2

4
CCBC

Sample Output 2

0

There may be no substrings that satisfy the condition.


Sample Input 3

36
CABACBBBBBAABABACCBCABCCABAABABBCBAC

Sample Output 3

136
I - Colored Ball

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

配点 : 500 点

問題文

1, 2, \ldots, N の番号がついた N 個の箱があり、はじめ箱 i には色 C_i のボールが 1 つ入っています。

Q 個のクエリが与えられるので、これらを順に処理してください。

各クエリは整数の組 (a,b) によって与えられ、その内容は以下の通りです。

  • 箱 a のボールをすべて箱 b に移し、その後箱 b に何種類の色のボールが入っているかを出力する。

ただし、箱 a や箱 b が空の場合もあることに注意してください。

制約

  • 1 \leq N, Q \leq 200000
  • 1 \leq C_i \leq N
  • 1 \leq a, b \leq N
  • a \neq b
  • 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ここで、 \text{query}_i は i 番目のクエリを意味する。

N Q
C_1 C_2 \ldots C_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

各クエリは次の形式で与えられる。

a b

出力

Q 行出力せよ。 i 行目には i 番目のクエリに対する答えを出力せよ。


入力例 1

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

出力例 1

1
2
1
1
3
  • 1 番目のクエリでは、箱 1 のボールをすべて箱 2 に移します。箱 2 には色 1 のボールが 2 つ入っている状態となるため、1 を出力します。

  • 2 番目のクエリでは、箱 6 のボールをすべて箱 4 に移します。箱 4 には色 2 のボールが 1 つ、色 3 のボールが 1 つ入っている状態となるため、2 を出力します。

  • 3 番目のクエリでは、箱 5 のボールをすべて箱 1 に移します。箱 1 には色 2 のボールが 1 つ入っている状態となるため、1 を出力します。

  • 4 番目のクエリでは、箱 3 のボールをすべて箱 6 に移します。箱 6 には色 1 のボールが 1 つ入っている状態となるため、1 を出力します。

  • 5 番目のクエリでは、箱 4 のボールをすべて箱 6 に移します。箱 6 には色 1 のボールが 1 つ、色 2 のボールが 1 つ、色 3 のボールが 1 つ入っている状態となるため、3 を出力します。


入力例 2

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

出力例 2

1
2
0

Score : 500 points

Problem Statement

There are N boxes numbered 1, 2, \ldots, N. Initially, box i contains one ball of color C_i.

You are given Q queries, which you should process in order.

Each query is given by a pair of integers (a,b) and asks you to do the following:

  • Move all the balls from box a to box b, and then print the number of different colors of balls in box b.

Here, the boxes a and b may be empty.

Constraints

  • 1 \leq N, Q \leq 200000
  • 1 \leq C_i \leq N
  • 1 \leq a, b \leq N
  • a \neq b
  • All input values are integers.

Input

The input is given from Standard Input in the following format, where \text{query}_i represents the i-th query:

N Q
C_1 C_2 \ldots C_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Each query is given in the following format:

a b

Output

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


Sample Input 1

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

Sample Output 1

1
2
1
1
3
  • For the first query, move all the balls from box 1 to box 2. Box 2 now contains two balls of color 1, so print 1.

  • For the second query, move all the balls from box 6 to box 4. Box 4 now contains one ball of color 2 and one ball of color 3, so print 2.

  • For the third query, move all the balls from box 5 to box 1. Box 1 now contains one ball of color 2, so print 1.

  • For the fourth query, move all the balls from box 3 to box 6. Box 6 now contains one ball of color 1, so print 1.

  • For the fifth query, move all the balls from box 4 to box 6. Box 6 now contains one ball of color 1, one ball of color 2, and one ball of color 3, so print 3.


Sample Input 2

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

Sample Output 2

1
2
0