問題文

整数 N と英大文字からなる長さ N の文字列 S が与えられます。

S の後ろの 2 文字を入れ替えた文字列を出力してください。

制約

• 2\le N\le 10
• N は整数
• S は英大文字からなる長さ N の文字列

入力例 1

3
EFG

出力例 1

EGF

EFG の後ろの 2 文字を入れ替えると EGF になります。したがって、 EGF を出力してください。

入力例 2

6
CENTER

出力例 2

CENTRE

入力例 3

2
PP

出力例 3

PP

問題文

整数 N と英大文字からなる長さ N の文字列 S が与えられます。

S に含まれる F を G に、 G を F に同時に置換した文字列を出力してください。

制約

• 1\le N\le 50
• N は整数
• S は英大文字からなる長さ N の文字列

入力例 1

3
EFG

出力例 1

EGF

EFG の F を G に、G を F に同時に置換すると EGF になります。したがって、 EGF を出力してください。

入力例 2

6
DIGGER

出力例 2

DIFFER

入力例 3

7
ATCODER

出力例 3

ATCODER

置換前後で文字が変わらない場合もあります。

問題文

整数 N と英大文字からなる長さ N の文字列 S が与えられます。

以下の条件を全て満たす整数の組 (i,j,k) の個数を求めてください。

• 1\le i < j < k \le N
• S_i= E
• S_j= G
• S_k= F

制約

• 3\le N\le 50
• N は整数
• S は英大文字からなる長さ N の文字列

入力例 1

16
ENGINEERGUILDFES

出力例 1

4

(i,j,k)=(1,3,14),(1,9,14),(6,9,14),(7,9,14) が条件を全て満たします。

入力例 2

3
EGG

出力例 2

0

条件を全て満たす整数の組は存在しません。

入力例 3

14
FGEFEUYGFEEGFE

出力例 3

8

問題文

整数 N と英小文字からなる N 個の文字列 S_1,S_2,\ldots,S_N が与えられます。ここで、S_i の長さは相異なることが保証されます。

N 個の文字列 S_1,S_2,\ldots,S_N を長い順に並び替え、それらの頭文字を大文字にして順に並べた文字列を出力してください。

制約

• 2\le N\le 10
• N は整数
• S_i は英小文字からなる長さ 1 以上 10 以下の文字列
• S_i の長さは相異なる

入力例 1

3
fes
engineer
guild

出力例 1

EGF

fes, engineer, guild を長い順に並び替えると engineer, guild, fes となります。これらの頭文字はそれぞれ e, g, f で、この頭文字を大文字にして連結した文字列は EGF です。したがって、 EGF を出力してください。

入力例 2

3
atcoder
heuristic
constest

出力例 2

HCA

入力例 3

4
https
gaishi
shukatsu
com

出力例 3

SGHC

問題文

整数 N,Q と英大文字からなる長さ N の文字列 S が与えられます。

Q 個のクエリが与えられるので、これらのクエリを順に処理した際の最終的な S を求めてください。

各クエリは以下の形式で与えられます。

• タイプ 1：1 x の形式で与えられる。 S の x 文字目と x+1 文字目を入れ替える。
• タイプ 2：2 x の形式で与えられる。 S の先頭 x 文字を削除する。

制約

• 1\le N\le 10^6
• 1\le Q\le 10^6
• N,Q は整数
• S は英大文字からなる長さ N の文字列
• タイプ 1 のクエリについて、そのクエリ時点での S の長さを L としたとき 1\le x\le L - 1
• タイプ 2 のクエリについて、そのクエリ時点での S の長さを L としたとき 1\le x\le L

入力例 1

7 3
ABCDEFG
1 1
2 4
1 2

出力例 1

EGF

各クエリを処理していくと S は以下のようになります：

• S の 1 文字目と 2 文字目を入れ替える。 S= BACDEFG となる。
• S の先頭 4 文字を削除する。 S= EFG となる。
• S の 2 文字目と 3 文字目を入れ替える。 S= EGF となる。

最終的な S は EGF となるので、 EGF を出力してください。

入力例 2

7 3
ATCODER
1 1
1 6
2 7

出力例 2

最終的な S が空文字列となる場合もあります。

入力例 3

16 6
ENGINEERGUILDFES
1 3
2 5
1 4
1 3
2 1
1 4

出力例 3

EURIGLDFES

問題文

H 行 W 列のグリッドが与えられます。上から i 行目、左から j 列目のマスをマス (i,j) と表します。各マスには E, F, G のいずれかの文字が書かれており、マス (i,j) に書かれた文字は与えられる文字列 S_i の j 文字目と同じです。

はじめ、マス (1,1) にコマが置かれています。あなたの目標はこのコマを四方向に隣接するマスに動かす操作を繰り返してマス (H,W) にコマが置かれた状態にすることです。

ただし、各操作で今いるマスと同じ文字が書かれたマスへ移動することはできません。

マス (H,W) にコマが置かれた状態にすることが可能か判定し、可能な場合は操作回数の最小値を求めてください。

制約

• 2\le H\le 1000
• 2\le W\le 1000
• H,W は整数
• S_i は E, F, G からなる長さ W の文字列

入力例 1

3 4
EEGE
GFFF
GFEE

出力例 1

7

マス (1,1) から順にマス (2,1),(2,2),(1,2),(1,3),(1,4),(2,4),(3,4) と順に動かしていけば良いです。

この場合の操作回数は 7 回で、 7 回未満でマス (3,4) にコマが置かれた状態にすることはできません。したがって、 7 を出力してください。

入力例 2

2 2
EE
FF

出力例 2

-1

マス (2,2) にコマが置かれた状態にすることはできません。したがって、 -1 を出力してください。

入力例 3

5 6
FEGFGF
FEEFEE
FFGGFE
GEGGEE
GGEGFE

出力例 3

9

問題文

H 行 W 列のグリッドが与えられます。上から i 行目、左から j 列目のマスをマス (i,j) と表します。各マスには E, F, G のいずれかの文字が書かれており、マス (i,j) に書かれた文字は与えられる文字列 S_i の j 文字目と同じです。

以下の条件を全て満たす 3 マスの組 (r_1,c_1),(r_2,c_2),(r_3,c_3) の個数を求めてください。

• 1\le r_1 < r_2 < r_3 \le H
• 1\le c_{\color{red}1\color{black}} < c_{\color{red}3\color{black}}<c_{\color{red}2\color{black}} \le W
• マス (r_1,c_1) に書かれた文字は E
• マス (r_2,c_2) に書かれた文字は F
• マス (r_3,c_3) に書かれた文字は G

制約

• 3\le H,W\le 2000
• H,W は整数
• S_i は E, F, G からなる長さ W の文字列

入力例 1

3 3
EGF
EGF
EGF

出力例 1

1

(r_1,c_1)=(1,1),(r_2,c_2)=(2,3),(r_3,c_3)=(3,2) のみが条件を満たします。

入力例 2

3 4
GGGG
FFFF
EEEE

出力例 2

0

条件を全て満たす 3 マスの組は存在しません。

入力例 3

7 5
FEGFG
FFEEF
EEFFG
GFEGE
GGEEG
GEGFE
GFFGF

出力例 3

4