背景

仙台には仙台駅を中心に南北線・東西線という 2 本の地下鉄が通っています。 ( wikipedia / 仙台市地下鉄 )

問題文

2 次元平面上に N 個の都市があります。i 番目の都市は座標 (x_i, y_i) に位置し、人口が p_i 人です。

あなたは都市を一つ選び、選んだ都市を基点として（ x 軸に平行な）東西方向・（ y 軸に平行な）南北方向に無限に伸びる地下鉄を敷設しようと考えています。

都市を適切に選ぶことで、地下鉄を利用できる人数の最大値を求めてください。 ただし、地下鉄を利用できる人とは、地下鉄が通る都市に住むすべての人を指します。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq x_i, y_i \leq 2 \times 10^5
• 1 \leq p_i \leq 10^9
• (x_i, y_i) \neq (x_j, y_j) \, (i \neq j)
• 入力はすべて整数

入力例 1

4
10 7 40
12 12 50
5 7 10
5 10 30

出力例 1

80

3 番目の都市を選ぶと、直線 x = 5, y = 7 上に地下鉄が敷設されます。 このとき、都市 1 、都市 3 、都市 4 に住む 40 + 10 + 30 = 80 人が地下鉄を利用でき、これが最大値となります。

入力例 2

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

出力例 2

3

座標 (1, 3) を基点とする地下鉄は敷設できないことに注意してください。

入力例 3

15
3 5 636708929
2 8 994903426
9 9 607399553
8 8 827889418
9 5 668774629
3 9 811132635
10 7 890433514
5 6 742283973
1 1 912497044
4 9 946700459
1 4 730139009
1 9 843207307
7 4 728535529
2 4 950182766
9 1 523704155

出力例 3

4851076007

答えは 32 bit 整数型に収まらない場合があります。

問題文

H 行 W 列からなるマス目に、以下の条件を全て満たすように整数を書きこみます。 ただし、上から h 行目、左から w 列目に書き込まれる整数を X_{h,w} と表します。

• 全てのマスに丁度1つずつ整数を書きこむ
• 書き込む整数は 0, 1, 2 のいずれか
• 1\le h\le H-1,1\le w\le W を満たす整数の組 (h,w) 全てについて、X_{h+1,w}-X_{h,w}\in\lbrace0,1\rbrace
• 1\le h\le H,1\le w\le W-1 を満たす整数の組 (h,w) 全てについて、X_{h,w+1}-X_{h,w}\in\lbrace0,1\rbrace
• 1\le h\le H-1,1\le w\le W-1 を満たす整数の組 (h,w) 全てについて、X_{h+1,w+1}-X_{h,w}\in\lbrace0,1\rbrace

このような書き込み方は何通りありますか。答えを 998244353 で割った余りを求めてください 。

制約

• 1 \leq H\leq 2\times 10^5
• 1 \leq W\leq 2\times 10^5
• 入力はすべて整数

部分点

• 追加の制約 H \leq 50,W\leq 50 を満たすデータセットに正解した場合は 10 点が与えられる

入力例 1

2 2

出力例 1

11

例えば、

00 01 11
00 11 22

等が満たします。

入力例 2

20 23

出力例 2

521442928

入力例 3

200000 200000

出力例 3

411160917

このサンプルは部分点の制約を満たしません。

問題文

(1,2,\ldots,N) の順列を以下では単に順列と呼びます。

正整数 N と順列 P が与えられます。

有向閉路と多重辺を持たない、頂点に 1 から N までの番号が付けられ、辺に番号が付けられていない N 頂点の有向グラフであって、辞書順最小トポロジカル順序が P と一致するようなものの個数を 998244353 で割った余りを求めてください。

制約

• 2\leq N\leq 2\times 10^5
• (P_1, P_2, \ldots,P_N) は (1,2, \ldots,N) の順列
• 入力はすべて整数

入力例1

3
1 3 2

出力例1

4

以下の 4 つの有向グラフが条件を満たします。

入力例2

5
1 2 3 4 5

出力例2

1024

入力例3

6
4 2 1 5 6 3

出力例3

4096

問題文

N\times N のマス目 S,T があり、各マスは白または黒で塗られています。それぞれのマス目の状態は N^2 個の文字で表現され、マス目 S の上から x 行目、左から y 列目にあるマスが黒色のとき S_{x,y} は #、白色のとき S_{x,y} は . となっています。 T も同様です。

マス目 S に対し、以下の操作を行うことができます。

• 整数 t,x (1\leq t\leq 2,1\leq x\leq N) を選ぶ。
• t=1 のとき、 S の x 行目にある各マスの色を右方向に 1 マス巡回シフトさせる。すなわち、 S_{x,1}S_{x,2}\ldots S_{x,N} を S_{x,N}S_{x,1}\ldots S_{x,N-1} で同時に置き換える。
• t=2 のとき、 S の x 列目にある各マスの色を下方向に 1 マス巡回シフトさせる。すなわち、 S_{1,x}S_{2,x}\ldots S_{N,x} を S_{N,x}S_{1,x}\ldots S_{N-1,x} で同時に置き換える。

上の操作を N^3 回以下行って S を T に一致させられるかどうか判定し、一致させられるならばその操作手順を一つ出力してください。

制約

• 2\leq N\leq 80
• S_{x,y},T_{x,y} は # または .
• N は整数

部分点

• 追加の制約 N\leq 4 を満たすデータセットに正解した場合は 10 点が与えられる。

入力例 1

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

出力例 1

Yes
4
1 3
2 3
2 1
1 1

S は以下のように変化します。

入力例 2

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

出力例 2

Yes
0

一度も操作を行いません。

入力例 3

13
.............
....#####....
......#......
......#......
......#......
......#......
.............
....#...#....
....#...#....
....#...#....
....#...#....
.....###.....
.............
....####.....
....#...#....
....####.....
....#........
....#........
.............
.....###.....
....#...#....
....#........
....#...#....
.....###.....
.............
.............

出力例 3

No

問題文

0 以上 M 以下の非負整数からなる長さ N の数列 A=(A_1,A_2,\dots,A_N) のうち、以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。

• すべての i=1,2,\dots,N に対して、 A_i + (A_{i-1} \& A_{i+1})=M である。ただし、 A_0 \coloneqq A_N,A_{N+1} \coloneqq A_1 とし、 \& はビットごとの論理積である。

制約

• 3 \leq N \leq 10^9
• 0 \leq M \leq 10^9
• 入力はすべて整数

入力例 1

3 2

出力例 1

4

条件を満たす A は (0,2,2), (2,0,2), (2,2,0), (1,1,1) の 4 つです。

入力例 2

3 0

出力例 2

1

条件を満たす A は (0,0,0) の 1 つです。

入力例 3

100 100

出力例 3

343406454

998244353 で割った余りを求めてください。

問題文

長さ 1 の整数列 A=(1) があります。 クエリが Q 個与えられるので順に処理してください。

クエリは以下の 3 種類です。

いずれも、各クエリ処理前の数列 A の長さを n とし、A=(a_{1},a_{2},\dots,a_{n}) とします。

• 1 x : A を長さ n+1 の数列 (x,a_{1},a_{2},\dots,a_{n}) に置き換える。
• 2 x : A を長さ 2n の数列 (x,a_{1},x,a_{2},\dots,x,a_{n}) に置き換える。
• 3 x : x>n ならば -1 を出力する。 x\le n ならば a_{x} を出力する。

制約

• 1 \leq Q \leq 2\times 10^5
• 1\leq x\leq 10^{9}
• 出力クエリが少なくとも1つ存在する
• 入力はすべて整数

入力例 1

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

出力例 1

-1
4
3

クエリ 1 前: A=(1)
クエリ 1 後: A=(4,1)
クエリ 2 後: A=(4,1)
クエリ 3 後: A=(3,4,1)
クエリ 4 後: A=(3,4,1)
クエリ 5 後: A=(3,3,3,4,3,1)
クエリ 6 後: A=(3,3,3,4,3,1)
となっています。

入力例 2

8
1 8
2 5
2 5
3 7
3 8
3 9
2 3
3 1

出力例 2

5
1
-1
3

問題文

N 個の石の山があり、はじめ i 番目の山には石が A_i 個あります。これらの山を使って Anna と Bob がゲームを行います。

ゲームでは、Anna を先手として二人が交互に以下の操作を行います。

• 石が 1 個以上残っている山 i\,(1\leq i \leq N) を選ぶ。山 i から 1 個以上の石を取り除く。ただし、操作後に山 i に残っている石の個数が、各山に残っている石の個数全体の最小値になっている必要がある。より形式的には、以下が成り立つように操作する必要がある。
  • 操作後に山 j に残っている石の数を A'_j とする (残っていなければ A'_j=0 とする)。 A'_i=\min\{A'_1,A'_2,\dots,A'_N\} が成り立つ。

操作が行えなくなった方が負けで、負けなかった方が勝ちです。両者が勝ちを目指して最適な行動を取るとき、どちらが勝つか判定してください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \leq T
• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9 \, (i=1,2,\dots,N)
• 1 つの入力に含まれるテストケースについて、 N の総和は 10^5 以下
• 入力はすべて整数

入力例 1

2
3
3 1 4
8
3 1 4 1 5 9 2 6

出力例 1

First
Second

1 番目のテストケースについて、最初に Anna が行うことのできる操作は以下のとおりです。

• 山 1 から 2 個以上の石を取り除く
• 山 2 から 1 個以上の石を取り除く
• 山 3 から 3 個以上の石を取り除く

問題文

長さ M の数列 B=(B_1,B_2,\dots,B_M) が 回文 であるとは、 B_i=B_{M+1-i} がすべての i=1,2,\dots,M について成り立つことをいいます。

また、数列 B が 擬回文 であるとは、 B を並べ替えて回文にできることをいいます。

長さ 2N の数列 A=(A_1,A_2,\dots,A_{2N}) が与えられます。 A には、 1,2,\dots,N がそれぞれちょうど 2 つ含まれます。

各 i=1,2,\dots,2N に対して、次の条件を満たす正整数の組 (l,r) \, (1 \le l \le r \le 2N) の個数を数えてください。

• l \leq i \leq r
• (A_l,A_{l+1},\dots,A_r) に、 A_i は 1 つだけ含まれる
• (A_l,A_{l+1},\dots,A_r) は擬回文である

制約

• 1 \le N \le 5 \times 10^5
• 各 1,2,\dots,N は A にちょうど 2 つ含まれる
• 入力はすべて整数

入力例 1

2
1 1 2 2

出力例 1

1 2 2 1

各 i に対して、条件を満たす正整数の組は以下のとおりです。

• i=1: (1,1)
• i=2: (2,2),(2,4)
• i=3: (1,3),(3,3)
• i=4: (4,4)

入力例 2

3
2 1 2 3 1 3

出力例 2

1 2 2 2 2 1

入力例 3

4
1 2 4 3 4 1 3 2

出力例 3

1 2 1 2 1 3 1 1

入力例 4

1
1 1

出力例 4

1 1

問題文

長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) と、正整数 K が与えられます。 A に以下の操作を好きな回数繰り返して出来る数列のうち、辞書順最大のものを求めてください。

• A の長さ K の連続部分列を削除する。厳密には、現在の A の長さを M として、整数 i\ (1\leq i\leq M-K+1) を選び、A=(A_1,A_2,\ldots,A_M) を (A_1,\ldots,A_{i-1},A_{i+K},\ldots,A_{M}) で置き換える。

制約

• 2\leq N\leq 3\times 10^5
• 1\leq K\leq N-1
• 1\leq A_{i}\leq N
• 入力は全て整数

入力例 1

9 3
1 2 3 4 1 2 3 4 1

出力例 1

4 4 1

辞書順最大の数列を得ることができる操作手順の一つです。

• (1,2,3,4,\color{red}{1}\color{black},\color{red}{2}\color{black},\color{red}{3}\color{black},4,1) \to (\color{red}{1}\color{black},\color{red}{2}\color{black},\color{red}{3}\color{black},4,4,1)\to(4,4,1)

入力例 2

6 1
1 6 4 2 3 5

出力例 2

6 5

辞書順最大の数列を得ることができる操作手順の一つです。

• (1,6,4,\color{red}2\color{black},3,5)\to(1,6,\color{red}4\color{black},3,5)\to(\color{red}1\color{black},6,3,5)\to(6,\color{red}3\color{black},5)\to(6,5)

入力例 3

6 5
6 5 4 3 2 1

出力例 3

6 5 4 3 2 1

一度も操作しないのが最適です。

問題文

この問題はインタラクティブな問題です。

N 頂点の完全無向グラフ G があります。完全無向グラフとは、任意の異なる 2 頂点間に無向辺が 1 つあるようなグラフです。
各辺は赤か青かで塗られていますが、その色は明かされていません。

あなたは次のような質問を 2N 回 まで行うことができます。

• 頂点 i と頂点 j \ (1 \leq i , j \leq N, \ i \neq j) を繋ぐ辺 (i,j) の色を聞く。

グラフ G の全域木であって、全ての辺が同じ色で塗られているものを 1 つ出力してください。
問題の制約下で、そのようなものが必ず存在することが証明できます。

ただし、回答は質問回数に含めません。

制約

• 3 \leq N \leq 5 \times 10^4
• N は整数

入出力

この問題はインタラクティブな問題です。
まず、N が標準入力に与えられます。

N

その後、あなたは質問を行うことが出来ます。
質問は標準出力に以下の形式で出力してください(末尾に改行を入れること)。
1 \leq i , j \leq N,\ i \neq j でなければならない点に注意してください。

? i j

質問が正当な場合、その質問への答え c が標準入力から与えられます。

辺 (i,j) の色が赤ならば R, 青ならば B が与えられます。

c

質問の形式が間違っている・質問を規定の回数より多く行なったなどの理由から質問が不正と判定された場合、質問への答えの代わりに F が与えられます。

F

この時、提出は不正解と判定され、ジャッジプログラムが終了します。

出力すべき全域木 T が分かったら、 i 番目の辺が頂点 u_i と 頂点 v_i を結んでいるとして、回答を標準出力に以下の形式で出力してください(最後に改行を入れること)。

!  
u_1 v_1  
u_2 v_2
\vdots  
u_{N-1} v_{N-1}

以下を全て満たすときに限り正解となります。

• 1 \leq u_i, v_i \leq N , \ u_i \neq v_i
• N-1 本の辺とそれらの両端の頂点からなるグラフは G の全域木である。
• N-1 本の辺は全て同じ色で塗られている。

回答を受け取った場合、答えの正誤に関わらずジャッジプログラムが終了します。

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
• 対話の途中で不正な出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。
• 答えを出力したら(またはF を受け取ったら)直ちにプログラムを正常終了してください。そうしなかった場合、ジャッジ結果は不定です。
• 特に、余計な改行も不正なフォーマットの出力とみなされるので注意してください。
• 高速な方法で入出力を行うことを推奨します。
• この問題のジャッジはアダプティブです。つまり、制約および以前の出力に矛盾しない範囲でグラフの辺の色が変わる場合があります。

入出力例

以下は N=3 であり、辺 (1,2), (2,3) が赤色、辺 (1,3) が青色のグラフの場合の対話例です。

問題文

整数 H, W, R が与えられます。

H 行 W 列のマス目があり、あなたはすべてのマスに整数を 1 つずつ書き込もうとしています。

上から i 行目、左から j 列目に書き込む整数を P_{i, j} とおくとき、 以下の条件を満たす書き込み方が存在するか判定してください。 もし存在する場合には、そのような書き込み方の一例を求めてください。

• (P_{1,1}, P_{1,2}, \ldots, P_{1, W}, P_{2, 1}, \ldots, P_{H, W}) は (1, 2, \ldots, H \times W) の並び替えである。

• どの 2 \times 2 マスを選んでも、その中にある 4 つの整数の積を HW + 1 で割った余りが R に等しい。

  • より正確には、任意の 1 \leq i \leq H-1, 1 \leq j \leq W-1 に対し、 P_{i, j} \times P_{i+1, j} \times P_{i, j+1} \times P_{i+1, j+1} \equiv R \pmod{HW + 1} が成立する。

各入力ファイルについて、テストケースを T 個解いてください。

制約

• 1 \leq T \leq 100
• 2 \leq H \leq 50
• 2 \leq W \leq 50
• 0 \leq R \lt HW + 1
• 入力はすべて整数

部分点

この問題の満点は 101 点である。

• 追加の制約 T = 1, H = W = 4, R = 8 を満たすデータセットに正解した場合は 10 点が与えられる。
• 追加の制約 H = W を満たすデータセットに正解した場合は、追加で 90 点（計 100 点）が与えられる。

入力例 1

3
2 2 4
5 5 17
6 6 30

出力例 1

Yes
1 2
3 4
No
Yes
22 9 31 11 33 32
23 10 2 25 3 19
20 21 8 1 30 13
36 29 16 17 24 7
12 35 27 14 18 34
26 6 28 15 5 4

この入出力例は追加の制約 H = W を満たします。

入力例 2

6
2 3 4
13 11 0
3 8 5
20 24 39
21 3 32
3 13 0

出力例 2

Yes
2 5 4
6 1 3
No
Yes
1 19 13 18 14 21 17 22
5 9 10 2 20 16 15 23
7 12 11 4 3 8 24 6
No
No
Yes
1 2 3 6 7 9 11 13 14 17 18 19 21
5 8 15 16 25 24 35 32 10 4 20 12 30
22 23 26 27 28 29 31 33 34 36 37 38 39

問題文

0 以上 M 未満の整数を一様ランダムに選ぶという操作を N 回行います。i 回目に選ばれた数を A_i とするとき \mathrm{mex}\big(A_1,A_2,\dots,A_N\big) の期待値を \text{mod}\,998244353 で求めてください。

ただし、\mathrm{mex}\big(A_1,A_2,\dots,A_N\big) で A_1,A_2,\dots,A_N に含まれない最小の非負整数を表します。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \leq T \leq 3 \times 10^5
• 1 \leq N,M \leq 8000
• 入力はすべて整数

部分点

• 追加の制約 T \leq 5,N \leq 100, M \leq 100 を満たすデータセットに正解した場合は 10 点が与えられる。

入力例 1

4
3 2
1 1
20 23
8000 8000

出力例 1

374341634
1
111675632
994279778

• 1 つ目のテストケースについて、 A として考えられるものは (0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1) の 8 つです。それぞれの \mathrm{mex} の値は 1,2,2,2,2,2,2,0 なので求める期待値は \dfrac{13}{8} です。
• 2 つ目のテストケースについて、A として考えられるものは (0) のみです。よって求める期待値は 1 です。

背景

RGB 値とは Red (赤)、 Green (緑)、 Blue (青) の各色を 0 以上 255 以下の値で指定することで、色を指定する値です。

(R, G, B) = (0, 0, 128) であればネイビーが、(255, 255, 0) であればイエローが指定されます。 一方、(R, G, B) がすべて同じ値であれば、白、灰色、黒のようにモノクロな色が指定されます。

問題文

表現可能な色の数が 256^3 では少ないと考えたあおばさんは、各パラメータが 0 以上 2 \times 10^5 以下の実数値をとるような拡張 RGB を考案しました。

パレットに N 個の絵の具があり、i 番目の色の拡張 RGB 値は (R, G, B) の順に (r_i, g_i, b_i) です。

拡張 RGB 値が (r, g, b) である色に対し、その色の鮮やかさを (r, g, b) の分散によって定義します。 たとえば (r, g, b) = (0, 120, 480) で表される色の鮮やかさは \frac{(0 - 200)^2 + (120 - 200)^2 + (480 - 200)^2}{3} = 41600 です。

あおばさんはパレットにある色のいくつかを混ぜることで鮮やかな色を作りたいと考えています。

複数の色を同時に混ぜると、拡張 RGB 値の各パラメータがもとの色の平均であるような色が生成されます。 混色後のパラメータの値は非整数になりうることに注意してください。

パレットにある N 個の絵の具の中からちょうど k 個を選び、それらを同時に混ぜるとき、 混ぜた後の色の鮮やかさとしてありうる最大値を \bmod{998244353} で求めてください。

以上の問題を k = 1, 2, \ldots, N について解いてください。

制約

• 2 \leq N \leq 2000
• 0 \leq r_i, g_i, b_i \leq 2 \times 10^5 \ (1 \leq i \leq N)
• 入力はすべて整数

部分点

• 追加の制約 N \leq 300 を満たすデータセットに正解した場合は 30 点が与えられる。

入力例 1

3
180 0 0
0 180 180
0 0 180

出力例 1

7200
5400
800

k = 2 のとき、2, 3 番目の色を混ぜることで拡張 RGB 値が (0, 90, 180) の色が生成されます。 この色の鮮やかさは \frac{(0-90)^2 + (90-90)^2 + (180-90)^2}{3} = 5400 です。

入力例 2

6
30594 32322 46262
63608 59020 98436
90150 32740 67209
82886 4627 54813
3112 67989 74995
60872 9967 9051

出力例 2

715162883
838096208
930330061
405079896
880764907
526006962

混ぜた後の色の拡張 RGB 値は非整数になることがあります。

問題文

頂点に 1 から N の番号が、辺に 1 から M の番号が付いた N 頂点 M 辺の単純連結無向グラフ G が与えられます。辺 i\;(1 \leq i \leq M) は頂点 u_i と v_i を結んでいます。
正の整数 K が与えられるので、頂点 1 から頂点 N への長さ K の歩道であって、同じ辺を連続して通らないものの個数を 998244353 で割った余りを求めてください。
厳密には、以下をすべて満たす長さ K+1 の数列 a=(a_0,a_1,\dots,a_K) の個数を 998244353 で割った余りを求めてください。

• a_i は 1 以上 N 以下の整数 (0 \leq i \leq K)
• a_0=1, a_K=N
• G において a_{i-1} と a_{i} を直接結ぶ辺が存在する (1 \leq i \leq K)
• a_{i-2} \ne a_i (2 \leq i \leq K)

制約

• 3 \leq N \leq 100
• N-1 \leq M \leq \dfrac{N(N-1)}{2}
• 1 \leq K \leq 10^9
• 1 \leq u_i < v_i \leq N
• i \ne j のとき (u_i,v_i) \neq (u_j,v_j)
• 与えられるグラフは単純連結無向グラフである
• 入力はすべて整数

部分点

• 追加の制約 N \leq 15 を満たすデータセットに正解した場合は 10 点が与えられる。

入力例 1

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

出力例 1

2

1 \to 2 \to 3 \to 5 \to 4 \to 6, 1 \to 3 \to 2 \to 4 \to 5 \to 6 の 2 つが条件を満たします。

入力例 2

11 11 2023
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
1 11

出力例 2

1

連続でなければ同じ辺を何度も通ることが可能です。

入力例 3

7 21 1000000000
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7

出力例 3

405422475

問題文

文字列 T が 良い文字列 であるとは、空文字列からはじめて以下の操作の繰り返しで T が得られることをいいます。

• T の任意の位置に 0100 を挿入する。

長さ N の 0,1,? からなる文字列 S が与えられます。 それぞれの ? を 0,1 のどちらかに置き換えることで得られる良い文字列の個数を 998244353 で割った余りを求めてください。

制約

• 4 \leq N \leq 500
• N は 4 の倍数
• S は長さ N の 0,1,? からなる文字列

入力例 1

8
0??0?100

出力例 1

2

S の ? を書き換えて作れる文字列のうち、 00100100 と 01000100 の 2 つが良い文字列です。

入力例 2

4
?0??

出力例 2

0

入力例 3

100
??0?????1?????0????0??0?????1?????0????0??0?????1?????0????0??0?????1?????0????0?????????0????1???0?

出力例 3

849386882

問題文

長さ N の (,) からなる文字列 S を考えます。
以下の M 個の条件 i \ (1 \leq i \leq M)のうち、満たすことのできる条件の数は最大でいくつかを求めてください。

• 条件 i : S の L_i 文字目から R_i 文字目までを取り出した文字列は、括弧の対応が取れている文字列である。

ここで、括弧の対応が取れている文字列を、次のうちいずれかの条件を満たす文字列と定義します。

• 空文字列
• ある括弧の対応が取れている空でない文字列 s,t が存在し、s,t をこの順に連結した文字列
• ある括弧の対応が取れている文字列 s が存在し、 (, s, ) をこの順に連結した文字列

制約

• 2 \leq N \leq 500
• 1 \leq M \leq 500
• 1 \leq L_i < R_i \leq N \ (1 \leq i \leq M)
• R_i - L_i + 1 は偶数
• 入力はすべて整数

入力例 1

5 3
1 2
4 5
2 5

出力例 1

2

S= (()() のとき、1 つ目の条件は満たしませんが、 2 つ目と 3 つ目の条件を満たしています。
3 つの条件を同時に満たす S は存在しないため、満たすことのできる条件は 2 つが最大です。
S 自身は括弧の対応が取れている文字列である必要はありません。

入力例 2

2 4
1 2
1 2
1 2
1 2

出力例 2

4

同じ条件が複数ある場合もあります。

入力例 3

32 11
25 32
19 32
11 24
20 31
22 25
21 26
17 22
30 31
23 28
4 15
19 22

出力例 3

8