A - Not Overflow

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

整数 N が与えられます。 N が -2^{31} 以上かつ 2^{31} 未満ならば Yes を、そうでないならば No を出力してください。

制約

  • -2^{63} \leq N < 2^{63}
  • N は整数である。

入力

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

N

出力

N が -2^{31} 以上かつ 2^{31} 未満ならば Yes を、そうでないならば No を出力せよ。


入力例 1

10

出力例 1

Yes

10 は -2^{31} 以上かつ 2^{31} 未満であるので、Yes を出力します。


入力例 2

-9876543210

出力例 2

No

-9876543210 は -2^{31} 未満であるので、No を出力します。


入力例 3

483597848400000

出力例 3

No

483597848400000 は 2^{31} 以上であるので、No を出力します。

Score : 100 points

Problem Statement

You are given an integer N. If N is between -2^{31} and 2^{31}-1 (inclusive), print Yes; otherwise, print No.

Constraints

  • -2^{63} \leq N < 2^{63}
  • N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

If N is between -2^{31} and 2^{31}-1 (inclusive), print Yes; otherwise, print No.


Sample Input 1

10

Sample Output 1

Yes

10 is between -2^{31} and 2^{31}-1, so Yes should be printed.


Sample Input 2

-9876543210

Sample Output 2

No

-9876543210 is less than -2^{31}, so No should be printed.


Sample Input 3

483597848400000

Sample Output 3

No

483597848400000 is greater than 2^{31}-1, so No should be printed.

B - Integer Sum

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 個の整数 A_1,A_2,\dots,A_N が与えられます。

N 個の整数を合計した値を求めてください。

制約

  • 1 \le N \le 100
  • 1 \le A_i \le 100
  • 入力はすべて整数

入力

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

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。


入力例 1

3
2 7 2

出力例 1

11

3 個の整数 2,7,2 が与えられます。

答えは 2 + 7 + 2 = 11 です。


入力例 2

1
3

出力例 2

3

Score : 100 points

Problem Statement

You are given N integers A_1,A_2,\dots, and A_N.

Find the sum of the N integers.

Constraints

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

Input

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

N
A_1 A_2 \dots A_N

Output

Print the answer.


Sample Input 1

3
2 7 2

Sample Output 1

11

You are given three integers: 2, 7, and 2.

The answer is 2 + 7 + 2 = 11.


Sample Input 2

1
3

Sample Output 2

3
C - A Reverse

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

整数 L,R と、英小文字のみからなる文字列 S が与えられます。
S の L 文字目から R 文字目までの部分を反転した(すなわち、 L 文字目から R 文字目までの文字の並びを逆にした)文字列を出力してください。

制約

  • S は英小文字のみからなる。
  • 1 \le |S| \le 10^5 (|S| は S の長さ)
  • L,R は整数
  • 1 \le L \le R \le |S|

入力

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

L R
S

出力

問題文の指示通り出力せよ。


入力例 1

3 7
abcdefgh

出力例 1

abgfedch

abcdefgh の 3 文字目から 7 文字目までの部分を反転すると、 abgfedch となります。


入力例 2

1 7
reviver

出力例 2

reviver

操作を行った結果が元の文字列と同一であることもあります。


入力例 3

4 13
merrychristmas

出力例 3

meramtsirhcyrs

Score : 200 points

Problem Statement

You are given integers L, R, and a string S consisting of lowercase English letters.
Print this string after reversing (the order of) the L-th through R-th characters.

Constraints

  • S consists of lowercase English letters.
  • 1 \le |S| \le 10^5 (|S| is the length of S.)
  • L and R are integers.
  • 1 \le L \le R \le |S|

Input

Input is given from Standard Input in the following format:

L R
S

Output

Print the specified string.


Sample Input 1

3 7
abcdefgh

Sample Output 1

abgfedch

After reversing the 3-rd through 7-th characters of abcdefgh, we have abgfedch.


Sample Input 2

1 7
reviver

Sample Output 2

reviver

The operation may result in the same string as the original.


Sample Input 3

4 13
merrychristmas

Sample Output 3

meramtsirhcyrs
D - Mex

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の整数からなる数列 A=(A_1,\ldots,A_N) が与えられます。

A_1,\ldots,A_N に含まれない最小の非負整数を求めてください。

制約

  • 1 \leq N \leq 2000
  • 0 \leq A_i \leq 2000
  • 入力は全て整数である

入力

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

N
A_1 \ldots A_N

出力

答えを出力せよ。


入力例 1

8
0 3 2 6 2 1 0 0

出力例 1

4

非負整数は 0,1,2,3,4,\ldots と続きます。
0,1,2,3 は A に含まれ、4 は A に含まれないので、答えは 4 です。


入力例 2

3
2000 2000 2000

出力例 2

0

Score : 200 points

Problem Statement

You are given a sequence of length N consisting of integers: A=(A_1,\ldots,A_N).

Find the smallest non-negative integer not in (A_1,\ldots,A_N).

Constraints

  • 1 \leq N \leq 2000
  • 0 \leq A_i \leq 2000
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

Print the answer.


Sample Input 1

8
0 3 2 6 2 1 0 0

Sample Output 1

4

The non-negative integers are 0,1,2,3,4,\ldots.
We have 0,1,2,3 in A, but not 4, so the answer is 4.


Sample Input 2

3
2000 2000 2000

Sample Output 2

0
E - FF

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君が運営する SNS「Twidai」にはユーザー 1 からユーザー N までの N 人のユーザーがいます。 Twidai では、ユーザーは別のユーザーをフォローすることや、フォローを解除することができます。

Twidai がサービスを開始してから、Q 回の操作が行われました。 i 回目 (1\leq i\leq Q) の操作は 3 つの整数 T _ i, A _ i, B _ i で表され、それぞれ次のような操作を表します。

  • T _ i=1 のとき:ユーザー A _ i がユーザー B _ i をフォローしたことを表す。この操作の時点でユーザー A _ i がユーザー B _ i をフォローしている場合、ユーザーのフォロー状況に変化はない。
  • T _ i=2 のとき:ユーザー A _ i がユーザー B _ i のフォローを解除したことを表す。この操作の時点でユーザー A _ i がユーザー B _ i をフォローしていない場合、ユーザーのフォロー状況に変化はない。
  • T _ i=3 のとき:ユーザー A _ i とユーザー B _ i が互いにフォローしているかをチェックすることを表す。この操作の時点でユーザー A _ i がユーザー B _ i をフォローしており、かつユーザー B _ i がユーザー A _ i をフォローしているとき、このチェックに対して Yes と答え、そうでないときこのチェックに対して No と答える必要がある。

サービス開始時には、どのユーザーも他のユーザーをフォローしていません。

すべての T _ i=3 であるような操作に対して、i が小さいほうから順番に正しい答えを出力してください。

制約

  • 2 \leq N \leq 10 ^ 9
  • 1 \leq Q \leq 2\times10 ^ 5
  • T _ i=1,2,3\ (1\leq i\leq Q)
  • 1 \leq A _ i \leq N\ (1\leq i\leq Q)
  • 1 \leq B _ i \leq N\ (1\leq i\leq Q)
  • A _ i\neq B _ i\ (1\leq i\leq Q)
  • T _ i=3 となる i\ (1\leq i\leq Q) が存在する
  • 入力される値はすべて整数

入力

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

N Q
T _ 1 A _ 1 B _ 1
T _ 2 A _ 2 B _ 2
\vdots
T _ Q A _ Q B _ Q

出力

T _ i=3 であるような i\ (1\leq i\leq Q) の個数を X として、X 行出力せよ。 j\ (1\leq j\leq X) 行目には j 番目の T _ i=3 であるような操作に対する答えを出力せよ。


入力例 1

3 9
1 1 2
3 1 2
1 2 1
3 1 2
1 2 3
1 3 2
3 1 3
2 1 2
3 1 2

出力例 1

No
Yes
No
No

Twidai には 3 人のユーザーがいます。 9 回の操作はそれぞれ次のようになっています。

  • ユーザー 1 がユーザー 2 をフォローします。そのほかにフォローしている/されているユーザーはいません。
  • ユーザー 1 とユーザー 2 が互いにフォローしているかチェックします。ユーザー 1 はユーザー 2 をフォローしていますが、ユーザー 2 はユーザー 1 をフォローしていません。この操作への正しい答えは No です。
  • ユーザー 2 がユーザー 1 をフォローします。
  • ユーザー 1 とユーザー 2 が互いにフォローしているかチェックします。ユーザー 1 はユーザー 2 をフォローしており、ユーザー 2 はユーザー 1 をフォローしています。この操作への正しい答えは Yes です。
  • ユーザー 2 がユーザー 3 をフォローします。
  • ユーザー 3 がユーザー 2 をフォローします。
  • ユーザー 1 とユーザー 3 が互いにフォローしているかチェックします。ユーザー 1 はユーザー 3 をフォローしておらず、ユーザー 3 もユーザー 1 をフォローしていません。この操作への正しい答えは No です。
  • ユーザー 1 がユーザー 2 のフォローを解除します。
  • ユーザー 1 とユーザー 2 が互いにフォローしているかチェックします。ユーザー 2 はユーザー 1 をフォローしていますが、ユーザー 1 はユーザー 2 をフォローしていません。この操作への正しい答えは No です。

入力例 2

2 8
1 1 2
1 2 1
3 1 2
1 1 2
1 1 2
1 1 2
2 1 2
3 1 2

出力例 2

Yes
No

同じユーザーに対して何度もフォロー操作をする場合があります。


入力例 3

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

出力例 3

No
No
No
No
Yes
Yes
No
No
No
Yes
Yes

Score : 300 points

Problem Statement

Takahashi runs an SNS "Twidai," which has N users from user 1 through user N. In Twidai, users can follow or unfollow other users.

Q operations have been performed since Twidai was launched. The i-th (1\leq i\leq Q) operation is represented by three integers T_i, A_i, and B_i, whose meanings are as follows:

  • If T_i = 1: it means that user A_i follows user B_i. If user A_i is already following user B_i at the time of this operation, it does not make any change.
  • If T_i = 2: it means that user A_i unfollows user B_i. If user A_i is not following user B_i at the time of this operation, it does not make any change.
  • If T_i = 3: it means that you are asked to determine if users A_i and B_i are following each other. You need to print Yes if user A_i is following user B_i and user B_i is following user A_i, and No otherwise.

When the service was launched, no users were following any users.

Print the correct answers for all operations such that T_i = 3 in ascending order of i.

Constraints

  • 2 \leq N \leq 10 ^ 9
  • 1 \leq Q \leq 2\times10 ^ 5
  • T _ i=1,2,3\ (1\leq i\leq Q)
  • 1 \leq A _ i \leq N\ (1\leq i\leq Q)
  • 1 \leq B _ i \leq N\ (1\leq i\leq Q)
  • A _ i\neq B _ i\ (1\leq i\leq Q)
  • There exists i\ (1\leq i\leq Q) such that T _ i=3.
  • All values in the input are integers.

Input

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

N Q
T _ 1 A _ 1 B _ 1
T _ 2 A _ 2 B _ 2
\vdots
T _ Q A _ Q B _ Q

Output

Print X lines, where X is the number of i's (1\leq i\leq Q) such that T _ i=3. The j-th (1\leq j\leq X) line should contain the answer to the j-th operation such that T _ i=3.


Sample Input 1

3 9
1 1 2
3 1 2
1 2 1
3 1 2
1 2 3
1 3 2
3 1 3
2 1 2
3 1 2

Sample Output 1

No
Yes
No
No

Twidai has three users. The nine operations are as follows.

  • User 1 follows user 2. No other users are following or followed by any users.
  • Determine if users 1 and 2 are following each other. User 1 is following user 2, but user 2 is not following user 1, so No is the correct answer to this operation.
  • User 2 follows user 1.
  • Determine if users 1 and 2 are following each other. User 1 is following user 2, and user 2 is following user 1, so Yes is the correct answer to this operation.
  • User 2 follows user 3.
  • User 3 follows user 2.
  • Determine if users 1 and 3 are following each other. User 1 is not following user 3, and user 3 is not following user 1, so No is the correct answer to this operation.
  • User 1 unfollows user 2.
  • Determine if users 1 and 2 are following each other. User 2 is following user 1, but user 1 is not following user 2, so No is the correct answer to this operation.

Sample Input 2

2 8
1 1 2
1 2 1
3 1 2
1 1 2
1 1 2
1 1 2
2 1 2
3 1 2

Sample Output 2

Yes
No

A user may follow the same user multiple times.


Sample Input 3

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

Sample Output 3

No
No
No
No
Yes
Yes
No
No
No
Yes
Yes