問題文

新進気鋭のプログラマーであるあなたは、TTPC (Tech Talk Presentation Cup) に興味を持ちました。

TTPC は第一回が A 年に、第二回は B 年に行われたようです。 その他の情報は得られませんでしたが、おそらく (B - A) 年ごとに行われているのだろうと考えました。

あなたは準備の時間を加味して、T 年以降（T 年ちょうども含む）に開催される最初の TTPC に参加しようと思いました。

T 年以降最初の TTPC は何年に開催されるでしょうか。

制約

• 入力は全て整数
• 1{,}000 \leq A \lt B \lt T \leq 3{,}000

入力例 1

2015 2019 2020

出力例 1

2023

• 2020 年以降最初の TTPC は 2023 年に開催されます。

入力例 2

2015 2019 2027

出力例 2

2027

• 2027 年以降、に 2027 年も含まれることに注意してください。

入力例 3

1000 2999 3000

出力例 3

4998

問題文

東京工業大学の正式名称は Tokyo Institute of Technology であり、また公式の略称は Tokyo Tech です。 東京工業大学に在学する rina さんは、AtCoder のコンテストの順位表を東京工業大学に所属する人のみになるようフィルタリングしようと思いました。 しかし、人によって所属の文字列が正式名称だったり略称だったり、また細かい表記揺れがあったりと変わるため、rina さんは *okyo*ech* というパターンを用いてフィルタリングをすることにしました。 rina さんは TTPC2200 の準備で忙しいので、通りすがりのあなたにフィルタリングプログラムを作成するよう依頼してきました。

整数 N が与えられます。続く N 行の i 行目に所属を表す文字列 S_i が与えられるので、その所属が *okyo*ech* 型の文字列ならば Yes を、そうでないなら No をそれぞれ出力してください。

ただし、文字列 T が *okyo*ech* 型の文字列であるとは、ある文字列 A, B, C が存在して、T が A + "okyo" + B + "ech" + C と書けることを言います。 ここで、+ は文字列の連結を表し、また A, B, C はそれぞれ空文字列である可能性があることに注意して下さい。

制約

• N は 1 \leq N \leq 50 を満たす整数
• S_i は英小文字のみからなる文字列
• 1 \leq \lvert S_i \rvert \leq 50

入力例 1

1
tokyoinstituteoftechnology

出力例 1

Yes

入力例 2

8
okyoech
tokyotech
titech
tokyotokyotechtech
tokyotecg
tttoookkkyyyooottteeeccchhh
tokyokogyodaigaku
tokyouniversityofagricultureandtechnology

出力例 2

Yes
Yes
No
Yes
No
No
No
Yes

• 東京工業大学でない大学などに対する答えも Yes となることがある点に注意して下さい。

背景

rian ちゃんは公園で N 個の整数からなる数列を拾いました。 rian ちゃんはこの数列を、友達の nari くんにプレゼントすることにしました。

ところが、よく見たところ rian ちゃんの拾った数列はいくつかの要素がかすれて読めなくなっていました。 そこで、nari くんが整数 X が好きだということを思い出した rian ちゃんは、かすれた要素それぞれに 0 以上 X 以下の整数を入れ、N 個全ての要素の排他的論理和を取った値がちょうど X になるようにしてから、nari くんに数列をプレゼントすることにしました。 果たして rian ちゃんは nari くんに数列をプレゼントできるでしょうか...？

問題文

自然数 N, X と数列 (a_1, a_2, \ldots, a_N) が入力として与えられます。 ただし、いくつかの a_i は情報が欠損しています。また、欠損した a_i が 0 \leq a_i \leq X であることがわかっています。

a_1 \text{ XOR } a_2 \text{ XOR } \cdots \text{ XOR } a_N = X

を満たすような数列に復元してください。

制約

• 入力はすべて整数である。
• 1 \leq N \leq 5 \times 10^5
• 0 \leq X \leq 10^9
• -1 \leq a_i \leq 10^9
  a_i = -1 のときは、その情報が欠損していることを意味する。

入力例 1

4 11
8 -1 1 5

出力例 1

8 7 1 5

入力例 2

6 7
-1 2 -1 4 -1 6

出力例 2

1 2 3 4 5 6

• このケースでは、これ以外にも条件を満たす数列が存在します。

入力例 3

1 2
3

出力例 3

-1

問題文

東工大生のアンちゃんは、あいちゃんと石取りゲームと呼ばれる 2 人で遊ぶゲームをしていましたが、必勝法が分かってしまったので飽きてしまいました。

そこで、アンちゃんは素数に着目した石取りゲームを考え、「素数取りゲーム」と名付けました。

素数取りゲームのルールは以下の通りです。

• 開始時には N 個の山があり、i 個目の山には X_i 個（X_i は素数）の石がある
• 2 人のプレイヤーが交互に、石が存在する山のうち 1 つを選びそこからいくつかの石を取っていく
• 一度に取ることができる石の数は素数個で、かつその山の残る石の数も 0 個または素数個である必要がある
• 先に石を取ることができなくなったプレイヤーが負け

新しく考えたルールですが、すぐにアンちゃんもあいちゃんも必勝法が分かってしまった様子です。

では、アンちゃんが先手、あいちゃんが後手で X_1 個, X_2 個, \ldots , X_N 個の石からなる N 個の山で素数取りゲームを行った時に、お互いに最適な行動を取るとどちらが勝つか求めてください。

制約

• 入力は全て整数
• 1 \le N \le 2 \times 10^5
• 2 \le X_i \le 10^6
• X_i は素数

入力例 1

1
13

出力例 1

An

• 先手のアンちゃんが最初に山から 13 個全てを取ればよいです。

入力例 2

2
17 13

出力例 2

An

• 先手のアンちゃんが 2 つめの山から 2 個取ると、後手のあいちゃんは 1 つ目の山と 2 つ目の山のどちらかから全て取ることしかできないので、アンちゃんが勝ちます。

入力例 3

6
49529 868033 52361 519803 19289 386501

出力例 3

Ai

問題文

N \times N マスの方眼に対して、上から i 行目、左から j 列目にあるマスに書かれた数を c_{i,j} で表します。

自然数 N が入力として与えられるので、以下の条件を満たすような配置が存在するか判定し、存在するならそのうちの一つを出力してください。

• 各マスに書かれている数は 1, 2, \ldots, N^2 のいずれかである
• 各マスに書かれている数は全て異なる
• 各行のマスに書かれた数の総和を N で割ったあまりが全て異なる
• 各列のマスに書かれた数の総和を N で割ったあまりが全て異なる

制約

• 入力は全て整数
• 1 \le N \le 1000

入力例 1

3

出力例 1

Yes
1 7 9
2 8 5
3 4 6

各行の総和を 3 で割ったあまりは、

• 1 + 7 + 9 = 17 \ なので \ 2
• 2 + 8 + 5 = 15 \ なので \ 0
• 3 + 4 + 6 = 13 \ なので \ 1

各列の総和を 3 で割ったあまりは、

• 1 + 2 + 3 = 6 \ なので \ 0
• 7 + 8 + 4 = 19 \ なので \ 1
• 9 + 5 + 6 = 20 \ なので \ 2

よって、この配置は条件を満たします。

入力例 2

2

出力例 2

No

問題文

1 から N の番号が付いた N 個の都市があります。 最初、これらの都市の間に道路はありません。

道路の建設案が M 個あり、i 番目の案は、費用 c_i 円で都市 s_i から都市 t_i (s_i \lt t_i) へ一方通行の道路を建設するというものです。

このうちのいくつかを採用して、都市 w から都市 x、都市 y から都市 z がそれぞれ通行可能となるようにしたいです。

上の条件を満たすのに必要な金額の最小値を求めてください。

制約

• 入力は全て整数
• 4 \leq N \leq 10^5
• 2 \leq M \leq 2 \times 10^5
• 1 \leq w \lt x \leq N
• 1 \leq y \lt z \leq N
• 1 \leq c_i \leq 10^9
• 1 \leq s_i \lt t_i \leq N
• w, x, y, z はそれぞれ相異なる
• i \ne j のとき (s_i, t_i) \ne (s_j, t_j)

入力例 1

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

出力例 1

6

• 建設案 1, 3, 4, 6 を採用することで総費用は 6 円となり、これが最小です。

入力例 2

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

出力例 2

Impossible

• どのように建設案を選んでも、指定された都市間が通行可能となることはありません。

入力例 3

5 8
1 3 2 5
42 2 3
32 2 4
12 3 5
94 1 4
21 4 5
79 1 2
22 1 5
90 1 3

出力例 3

133

問題文

九頭龍さんは、ある女の子から英小文字のみからなる長さ N の回文 S をもらいました。

しかし、九頭龍さんの弟子のあいちゃんが、この回文に以下のようないたずらをしてしまいました。

• S の i \ (1 \leq i \leq N) 番目の文字を異なる英小文字に変更する、という操作を ちょうど K 回行う
  （ただし、同じ位置の文字を複数回選ぶこともあるものとします）

いたずらをされた後の文字列 T と整数 K が与えられるので、元の回文としてありうるものが何通りあるかを 10^9 + 7 で割ったあまりを求めてください。

制約

• N は 1 \leq N \leq 2 \times 10^{5} を満たす整数
• K は 0 \leq K \leq 10^{9} を満たす整数
• |T| = N
• T は英小文字のみからなる

入力例 1

5 1
abbaa

出力例 1

2

• aabaa, abbba が条件を満たします。

入力例 2

4 1
aaaa

出力例 2

0

• 操作をちょうど K 回行うことに注意してください。

入力例 3

1 100
a

出力例 3

26

入力例 4

11 7
abracadabra

出力例 4

1019576

問題文

この世界には N 個の国が存在し、これらの国には 1, 2, 3, \ldots, N の番号が付いています。 N 個の国々はいままで全く協力をし合ってきませんでしたが、国ごとの格差が大きくなり、支援を求める国々が増えてきたので国交を結びお互いに支援をし合うことにしました。

各国の現在の状況は、2 つの整数 X_i, P_i で表され、X_i は国 i の支援の最大授受量、P_i は支援の量に応じて助けられる国民の人数を表しています。

正確には、
X_i \ge 0 の国は他国への支援を行える国で、1 年間で合計 |X_i| までの支援を行うことができます。
X_i < 0 の国は他国からの支援を受けられる国で、1 年間で合計 |X_i| までの支援を受けることができます。
また、国 i が他国から合計 x \ (x \le |X_i|) の支援を受けると、P_i \times x 人の国民を助けられることが分かっています。

今現在どの国同士も国交は結んでおらず、これから Q 年間の国交を結ぶ予定が立っています。 その予定は 1 年に一つの国交が結ばれるものになっており、j 年目のはじめには国 a_j と国 b_j が国交を結ぶ予定です。

この Q 年間予定に従って順に国交を結んでいったとき、j 年目に支援で救える人数の最大値を各 j に対して求めてください。

ただし、ある国が支援を行うことができる国は、直接国交を結んでいる国、または複数の国交を経由して間接的に繋がっている国とします。

制約

• 入力は全て整数
• 2 \le N \le 10^5
• 1 \le Q \le \min(10^5, N(N-1)/2)
• 0 \le |X_i| \le 10^9
• \sum |X_i| \le 10^9
• 1 \le P_i \le 10^9 \ (X_i < 0)
• P_i = 0 \ (X_i \ge 0)
• 1 \le a_i, b_i \le N
• a_i \ne b_i
• i \ne j のとき (a_i, b_i) \ne (a_j, b_j)

入力例 1

3
2 0
3 0
-4 2
2
1 3
1 2

出力例 1

4
8

• 1 年目には、国 1 から国 3 に量 2 の支援を行うと、4 人助けることができます。
• 2 年目には、国 1 から国 3 に量 1 の支援と、国 2 から国 3 に国 1 を経由して量 3 の支援を行うと、合計 8 人助けることができます。

入力例 2

4
-5 1
-3 3
1 0
6 0
5
1 4
1 2
2 4
2 3
3 4

出力例 2

5
12
12
13
13

入力例 3

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

出力例 3

0
0
0

• 支援をすることのできる国が存在しないので、国交をいくら結んでも助かる人数は 0 人です。

問題文

\mathbb{N}を正の整数全体の集合として、f:\mathbb{N}\rightarrow\mathbb{N} を次のように定めます。

f(x):=\begin{cases}f\left(\frac xP\right)&\text{if}\quad x\equiv 0 \pmod{P}\\x&\text{otherwise}\end{cases}

整数 (P,Q,L,R) が与えられるので、次の値を一行で出力してください。

\text{ans}=\displaystyle\left(\prod_{i=L}^{R}f(i)\right) \ \bmod Q

制約

• 入力は全て整数
• 2\leq P, Q \leq 10^7
• 1\leq L\leq R\leq 10^{18}

入力例 1

2 5
6 9

出力例 1

4

• f(6)\times f(7)\times f(8)\times f(9)=3\times 7\times 1\times 9=189 なので、出力すべき値は 189 \bmod 5=4 となります。

入力例 2

3 3
57 61

出力例 2

1

• f(57)=19 であることに注意してください。

入力例 3

65536 2
7 9

出力例 3

0

入力例 4

7878 78787
1234 56789

出力例 4

14334

入力例 5

2 4
1 81357343004

出力例 5

1

問題文

次の数列 a = (a_0, a_1, \ldots , a_N) を考えます。

\begin{aligned} a_i = \begin{cases} x & ( \ i = 0 \ ) \\ y & ( \ i = 1 \ ) \\ a_{i-1} + a_{i-2} & ( \ \text{otherwise} \ ) \end{cases} \end{aligned}

アリスは動的計画法を用いて a_N を求めることにしました。具体的には次のようにしました。

1. 配列 a を用意する
2. a_{0} = x, \ a_{1} = y, \ a_{i} = 0 \ (i > 1) と初期化する
3. i = 2, 3, \ldots , N に対して、a_{i} に a_{i-1}+a_{i-2} を代入する

上記の手順の 3. において i が小さい順に更新していくと正しい a_{N} の値が求まります。 しかし、アリスは無計画なので i を適当な順番で更新しました。 このとき、更新の順番は (N-1)! 通りありますが、それぞれについて最終的に a_{N} に書き込まれている値を求め、その合計を 10^9+7 で割ったあまりを計算してください。

制約

• 入力は全て整数
• 0 \le x, y \le 10^9
• 2 \le N \le 10^6

入力例 1

0 1 3

出力例 1

3

• i を 2, 3 の順に更新すると a_{N} の値は 2 に、i を 3, 2 の順に更新すると a_{N} の値は 1 になり、合計は 3 です。

入力例 2

0 0 5

出力例 2

0

• どのような順番で操作を行ったとしても、最終的に a_{N} に書き込まれている値は 0 です。

入力例 3

1 1 6

出力例 3

117

入力例 4

12345 67890 1000000

出力例 4

418969939

問題文

長さ N の 0 と 1 からなる文字列 S, T が与えられます。

以下の操作を考えます。

• 1 \leq x \leq N となる整数 x を選び、文字列 S = S_1\ldots S_N を S_1\ldots S_x と S_{x+1}\ldots S_N に分け、それぞれ巡回右シフトをしてくっつける

ただし、文字列 U = U_1\ldots U_M の巡回右シフトとは U_1\ldots U_{M-1}U_M を U_MU_1\ldots U_{M-1} に変更することを意味します。また、x=N の時は文字列 S 全体を巡回右シフトします。 例えば、文字列 S=01001 に対して x=3 として操作を行うと、文字列はまず 010 と 01 にわけられ、それぞれを巡回右シフトすると 001 と 10 になるため、操作の結果として得られる文字列は 00110 となります。

この操作を文字列 S に対して任意回数行うことで、文字列 T と一致させることが出来るか判定してください。 出来ない場合は MuriyarokonnNaN を 1 行に出力、 出来る場合は最小の操作回数を 1 行に出力してください。

制約

• N は 1 \leq N \leq 10^{5} を満たす整数
• S と T は 0 と 1 からなる文字列
• \lvert S \rvert = \lvert T \rvert = N
• S に含まれる 0 の数と T に含まれる 0 の数は等しい
• S に含まれる 1 の数と T に含まれる 1 の数は等しい

入力例 1

6
010101
010110

出力例 1

3

以下のような順番で操作を行うことで、文字列 S を文字列 T に一致させることが出来ます。

• x=1 として操作を行う
• x=5 として操作を行う
• x=6 として操作を行う

この時、文字列 S は操作によって 010101 \to 011010 \to 101100 \to 010110 と変化します。

入力例 2

18
111101101001101001
111101101001101001

出力例 2

0

操作をしなくてもすでに一致しています。

入力例 3

18
011110100101000100
000110010011100110

出力例 3

8

問題文

x の多項式 f(x) が文字列 S として与えられます。 ここで S は次の BNF 表記の <expr> シンボルで表されます。

<expr> ::= <term> | <expr> "+" <term> | <expr> "-" <term>
<term> ::= <factor> | <term> "*" <factor>
<factor> ::= <value> | <value> "^" <number>
<value> ::= <number> | "x" | "(" <expr> ")"
<number> ::= 1 以上 10^9 未満の整数　ただし先頭の 0 は省略される

記号はそれぞれ以下の意味を表します。

• x: x
• +: 足し算
• -: 引き算
• *: 掛け算、ただし足し算 + や引き算 - よりも先に計算される
• ^: 累乗、ただし足し算 + や引き算 - や掛け算 * よりも先に計算される

例えば、以下の文字列は上の <expr> シンボルになり得ます。

• x^2+3*x^1+5
  • f(x) = x^2 + 3\times x^1 + 5
• 1+2-3+4*5
  • f(x) = 1 + 2 - 3 + 4 \times 5
• ((x^123+1)^456)^789
  • f(x) = \left( \left(x^{123} + 1\right)^{456}\right)^{789}
• ((x))
  • f(x) = \left(\left(x\right)\right)
• 1^1*1
  • f(x) = 1^1 \times 1

また、以下の文字列は上の <expr> シンボルになり得ません。

• 2x
• 0^0
• 2^x
• -1
• 2^(1+2)
• 1000000000
• 007

f(x) の \bmod{10^K} での零点の数、すなわち f(n) \equiv 0 \pmod{10^K} を満たす 0 以上 10^K 未満の整数 n の個数を求めてください。

制約

• 入力は全て整数
• 1 \leq K \leq 9
• 1 \leq |S| \leq 100

入力例 1

2
x^2-x

出力例 1

4

• 入力される多項式は f(x) = x^2 - x を表しています。
• 以下の通り、n=0, 1, 25, 76 が条件を満たします。
  • f(0) = 0
  • f(1) = 0
  • f(25) = 600 \equiv 0 \pmod{100}
  • f(76) = 5700 \equiv 0 \pmod{100}

入力例 2

8
(((x))^234567890*1^1*1+(x^2)^2)

出力例 2

1000128

• 入力される多項式は f(x) = \left(\left(\left(x\right)\right)^{234567890} \times 1^1 \times 1+\left(x^2\right)^2\right) を表しています。

入力例 3

9
50+(2019-x+(x^3-x)^2019)*x^1

出力例 3

6

• 入力される多項式は f(x) = 50+\left(2019-x+\left(x^3-x\right)^{2019}\right) \times x^1 を表しています。

問題文

1 から N までの番号がつけられた N 個の頂点を持つ木があります。 この木の i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。

この木に対し、頂点 r を根としたときの転倒数を以下のように定義します。

• 頂点 r から頂点 u の単純パスの端点または辺上に頂点 v が含まれるような組 (u, v) \ (u \lt v) の個数

1 以上 N 以下の全ての整数 r に対し、頂点 r を根としたときの転倒数を求めてください。

制約

• 入力は全て整数
• 2 \leq N \leq 10^{5}
• 1 \leq A_i, B_i \leq N
• 与えられるグラフは木である。

入力例 1

3
1 3
2 3

出力例 1

1
2
2

• 頂点 1 を根としたときの転倒数は、(u, v) = (2, 3) より 1 です
• 頂点 2 を根としたときの転倒数は、(u, v) = (1, 2), (1, 3) より 2 です
• 頂点 3 を根としたときの転倒数は、(u, v) = (1, 3), (2, 3) より 2 です。

入力例 2

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

出力例 2

2
3
4
3
7
7
9

問題文

双子のユーリくんとムーリくんは、見た目はそっくりですが、性格は正反対です。 例えば、ユーリくんは有理数が大好きですがムーリくんは無理数が大好きです。 これから二人は、N 個のコップを使って次のようなゲームをします。

• はじめ、i 番目のコップには水が W_i リットル入っており、2 つの数 l_i, u_i \ (l_i < u_i) が定められている。
• 先手から交互に操作を行い、操作を行えなくなった方を負けとする。

ただし、操作は以下の通りです。

1. 整数 k\ (1 \le k \le N) を選ぶ。k 番目のコップに残っている水の量を R_k リットルとする。
2. l_k \le x \le u_k かつ x \le R_k を満たす x を選び、k 番目のコップから水をちょうど x リットル飲む。 ただし、x としてユーリくんは有理数を、ムーリくんは無理数を選ばなければならない（条件を満たす k と x の組が存在しない時、操作が行えないとみなす）。

W_i, l_i, u_i の値を全て整数にする代わりに、ムーリくんは自分の手番を選べることになりました。 お互いが最適な行動をしたとき、どちらが勝つか判定してください。

制約

• 入力は全て整数
• 1 \le N \le 2 \times 10^5
• 1 \le W_i \le 10^9
• 1 \le l_i < u_i \le 10^9

入力例 1

2
8 2 5
7 5 6

出力例 1

Muri

• ムーリくんの戦略の 1 つは次のようなものです。
  • ムーリくんは先手を選び、i=1, x = 5- \pi / 4 として操作を行います。（1 番目のコップには水が 3+ \pi /4 リットル残ります）
  • その後、ユーリくんが i=1, x=2 として操作した場合は i=2, x = 5+ \pi /4 として、ユーリくんが i=2, x=11/2 として操作した場合は i=1, x = 2+ \pi /4 として操作をすることで、次の手番にユーリくんは操作ができなくります。

入力例 2

1
1 1 2

出力例 2

Yuri

• 1 \le x \le 2 かつ x \le 1 を満たす x は x=1 のみであり、ユーリくんのみが操作を行えます。整数も有理数であるためユーリくんは x として整数も選べることに注意してください。

入力例 3

5
12 1 100
11 2 8
1 5 7
7 5 7
29 4 5

出力例 3

Muri

問題文（一行）

S から G までの自己回避歩行 (self-avoiding walk) の数が N となるようなグリッドマップを作って出力して下さい。

問題文（詳細）

oneesan は以下の問題を高速に解くことが出来ます。

N,H,W と以下の条件を満たす高さ H、幅 W のグリッドマップが与えられます。

• 高さ H 幅 W のグリッドマップは、H 個の長さ W の文字列 S_1, S_2, \ldots, S_H で表される。
• 各マスはそれぞれ壁 # 、空き地 . 、始点 S 、終点 G の 4 文字のどれかで表される。
• 外周はすべて壁 # である。
• 始点 S と終点 G がそれぞれちょうど 1 マスずつ存在する。

グリッドマップ上で、S から G まで、上下左右に隣接した壁 # 以外のマスへの移動を繰り返して到達した時の、始点と終点を含めた通ったマスの列をパスとします。 パス P, Q が異なるとは、通ったマスの列の長さが違うか、P_i \ne Q_i となる i が存在することを言います。 パスの中でも、自己回避歩行 (self-avoiding walk) を、同じマスを 2 回通らないパスとします。 与えられたグリッドマップで、異なる自己回避歩行が何通りあるか調べ、それが N と等しいか答えて下さい。 等しい場合は Yes、そうでない場合は No と一行に出力して下さい。

oneesan は上述の能力を用いて自己回避歩行を数えるのが好きですが、自分でグリッドマップを生成して数えるのはつまらないと思いました。 そこで、oneesan はあなたにグリッドマップの生成をお願いすることにしました。

N が与えられるので、oneesan が Yes と出力するようなグリッドマップを出力して下さい。 ただし、グリッドマップには oneesan の仕様上の制限がいくつかあります。具体的には出力の項を読んで下さい。 この制約下で必ず解が存在することが言えます。また、制約さえ満たせばどのような解を出力しても構いません。

制約

• N は 0 \leq N \leq 2{,}019 を満たす整数

入力例 1

2

出力例 1

4 4
####
#S.#
#.G#
####

この出力以外にも正解となる出力が存在します。

入力例 2

8

出力例 2

5 9
#########
#S......#
#.#.#.#.#
#......G#
#########

入力例 3

184

出力例 3

6 6
######
#S...#
#....#
#....#
#...G#
######

入力例 4

1936

出力例 4

8 27
###########################
#.........................#
#.S####.#####.####...###..#
#...#.....#...#...#.#...#.#
#...#.....#...####..#.....#
#...#.....#...#.....#...G.#
#...#.....#...#......###..#
###########################