問題文

N 個の異なる整数 a_1, a_2, ..., a_N と整数 M が与えられます。

1 以上 M 以下のそれぞれの整数 i について、a_1, a_2, ..., a_N のうち i と互いに素であるものの個数を求めてください。

注釈

二つの整数 a と b が 互いに素 であるとは、a と b をともに割り切る正の整数が 1 以外に存在しないことをいいます。

例えば、6 と 7 は互いに素ですが、6 と 8 はともに 2 で割り切れるため互いに素ではありません。

制約

• 1 ≤ N, M ≤ 10^5
• 1 ≤ a_i ≤ 10^5
• a_i はすべて異なる。
• 入力値はすべて整数である。

入力例 1

4 3
6
7
8
9

出力例 1

4
2
2

6, 7, 8, 9 のうち、

• 1 と互いに素であるものは 6, 7, 8, 9 の 4 個
• 2 と互いに素であるものは 7, 9 の 2 個
• 3 と互いに素であるものは 7, 8 の 2 個

です。

入力例 2

1 5
100000

出力例 2

1
0
1
0
0

入力例 3

5 7
14142
17320
22360
24494
26457

出力例 3

5
1
3
1
3
0
5

問題文

次をすべて満たすようなマス目を構成してください。この問題の制約下で、このようなマス目が必ず存在することが保証されます。

• マス目の各マスは白か黒で塗られている
• マス目の縦横の長さをそれぞれ N,M としたとき、N,M は 1 以上 100 以下である
• 一番左上のマスから一番右下のマスまで、白く塗られたマスだけを通って右または下に 1 マス進むことを繰り返して辿り着く方法はちょうど K 通りある

制約

• 0 \leq K \leq 10^{18}
• K は整数である

入力例 1

4

出力例 1

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

一番左上のマスから一番右下のマスへ、右または下にのみ進むことを繰り返して辿り着く方法は、この例の場合 4 通りです。

入力例 2

18

出力例 2

4 4
...#
....
....
#...

問題文

N 頂点の木があります。i 本目の辺は、頂点 A_i と B_i を結んでいます。

次のクエリ Q 個に答えてください。

• 頂点 v_i からちょうど k_i 本の辺を引き返すことなしに通って辿り着くことのできる頂点の個数を求めよ。

制約

• 1 \leq N,Q \leq 10^5
• 1 \leq A_i,B_i \leq N(1\leq i\leq N-1)
• 1 \leq v_i \leq N(1\leq i\leq Q)
• 0 \leq k_i \leq N - 1(1\leq i\leq Q)
• 入力で与えられるグラフは木である
• 入力はすべて整数である

入力例 1

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

出力例 1

1
2
1
0
1

• 1 つめのクエリに対し、頂点 1 からちょうど 0 本の辺を通って辿り着くことのできる頂点は頂点 1 のみです。よって、1 を出力します。
• 2 つめのクエリに対し、頂点 2 からちょうど 1 本の辺を通って辿り着くことのできる頂点は頂点 2,3 です。よって、2 を出力します。
• 3 つめのクエリに対し、頂点 3 からちょうど 2 本の辺を通って辿り着くことのできる頂点は頂点 4 のみです。よって、1 を出力します。
• 4 つめのクエリに対し、頂点 4 からちょうど 4 本の辺を通って辿り着くことのできる頂点はありません。よって、0 を出力します。
• 5 つめのクエリに対し、頂点 5 からちょうど 1 本の辺を通って辿り着くことのできる頂点は頂点 3 のみです。よって、1 を出力します。

入力例 2

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

出力例 2

1
3
3
0
0
1
2
2
2
0
1
1
1
2
2
1
1
2
3
0
1
3
2
1
0
1
1
2
2
1
1
1
2
2
1

問題文

長さ N の非負整数からなる数列 l が与えられます。

以下の条件を満たすような長さ N の文字列 s が存在するかどうかを判定してください。なお、文字の種類数に制限はないものとします。

• 条件：1 以上 N 以下のそれぞれの整数 i について、s[1:i] と s[N-i+1:N] の最長共通接頭辞の長さは l_i である

注釈

• s[i,j] (i \leq j) は文字列 s の i 文字目から j 文字目までの部分文字列を指します。 例えば、s= ABCBC のとき、s[2:4] は BCB，s[4:5] は BC となります。

• 文字列 s,t の共通する接頭辞のうち、最長のものを s,t の最長共通接頭辞と呼びます。 例えば s= ABCBC，t= ABD のとき、最長共通接頭辞は AB となり、s= ABC，t= BCD のとき最長共通接頭辞は空文字列となります。

制約

• 1 \leq N \leq 3 \times 10^{5}
• 0 \leq l_i \leq i
• 与えられる入力は全て整数

入力例 1

3
1 0 3

出力例 1

Yes

• 例えば aba という文字列が条件を満たします。

入力例 2

2
1 0

出力例 2

No

• 長さ 2 の文字列は aa のような同じ文字の繰り返しで表せる文字列と、ab のような異なる 2 つの文字からなる文字列がありますが、どちらも条件を満たしません。

入力例 3

29
1 0 3 1 1 1 0 6 1 1 1 0 6 1 1 1 0 6 1 1 1 0 6 1 1 1 1 0 29

出力例 3

Yes

入力例 4

18
1 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 17 18

出力例 4

No

問題文

すぬけ君は 1 から N の番号がついた N 頂点の有向グラフを持っています。はじめ、このグラフには辺はありません。 すぬけ君の仕事はこのグラフに M 本の辺を追加して、任意の頂点のペア (u,v) について u から v へと辺を辿って到達できるようにすることです。

辺の追加には長さ M の数列 a,b を用います。 すぬけ君は a,b をそれぞれ自由に並び替えたあと (a,b 間で要素の交換をすることはできません)、これらの数列を使ってこのグラフに M 本の有向辺を追加します。

すぬけ君は i 番目の辺として、以下のどちらかの辺を追加することができます。

• 頂点 a_i から b_i へ向かう有向辺
• 頂点 b_i から a_i へ向かう有向辺

すぬけ君の仕事は達成可能ですか？可能ならばそのような辺の追加仕方の一例を示してください。

制約

• 1 \leq N , M \leq 2 \times 10^{5}
• 1 \leq a_i, b_i \leq N
• 与えられる入力は全て整数

入力例 1

3 6
1 2 3 1 1 1
3 2 1 1 1 2

出力例 1

Yes
1 > 2
1 < 2
1 > 3
3 > 1
1 < 1
2 > 1

• 以下の図のようなグラフを構成することで、すぬけ君は仕事を達成することが可能です。
• 最終的なグラフに多重辺や自己ループが含まれていても構わないことに注意してください。
  

入力例 2

3 1
1
2

出力例 2

No

• どのように辺を追加してもすぬけ君は仕事を達成することができません。

入力例 3

13 29
2 8 4 5 5 8 2 9 2 5 9 4 3 8 4 2 12 4 4 12 8 8 3 12 3 9 4 8 9
6 1 1 11 12 6 9 12 6 13 10 11 13 6 10 10 11 3 10 13 10 13 7 7 11 7 11 10 12

出力例 3

Yes
2 > 6
12 < 1
5 > 1
4 > 11
2 < 12
12 < 6
4 < 9
3 > 12
8 < 6
9 > 13
4 < 10
3 < 11
4 < 13
2 < 6
8 > 10
5 > 10
4 < 11
12 < 3
8 < 10
9 < 13
4 > 10
9 < 13
8 > 7
8 < 7
5 < 11
2 < 7
9 < 11
8 < 10
3 > 12