問題文

kenkooooさんはSoundHound社で働いています。彼は会社の知名度を上げるため、SoundHoundに名前が似ている言葉を見つけてマーケティングを行うことにしました。手始めに、2 単語からなる言葉で、それぞれの単語の頭文字を順につなげるとSHとなるような単語を似ていると見なすことにしました。

あなたの仕事は、2 単語 X Y からなる言葉が与えられたとき、頭文字を順につなげるとSHとなるか判定することです。

制約

• 与えられる単語は英大文字からなる
• 単語の長さは 1 以上 10 以下である

入力例 1

SAINT HELENA

出力例 1

YES

入力例 2

SOUND HOUND

出力例 2

YES

入力例 3

SOUND SPIDER

出力例 3

NO

入力例 4

S H

出力例 4

YES

入力例 5

X Y

出力例 5

NO

問題文

kenkooooさんはSoundHound社で働いています。彼は今日、音量を調整する機能を作ることにしました。

この機能では、n 秒の間毎秒与えられる入力に対し、ある大きさの音量を出力します。i 秒目の入力を a_i とします。もし、 a_i が出力の下限 L を下回っていた場合、出力は L とし、a_i が上限 R を上回っていた場合、出力を R とします。どちらでもないときは、出力を a_i とします。n 秒間の入力 a_i、L と R が与えられるので、n 個の出力 b_i を得るプログラムを書いてください。

制約

• 1≦n≦10^5
• 1≦a_i≦10^5
• 1≦L≦R≦10^5

入力例 1

4 2 3
1 4 2 3

出力例 1

2 3 2 3

• a_1(=1) について、下限 L(=2) を下回っているため、L を出力します。
• a_2(=4) について、上限 R(=3) を下回っているため、R を出力します。
• a_3, a_4 については、そのまま出力します。

入力例 2

3 1 10
3 3 4

出力例 2

3 3 4

入力例 3

1 3 3
3

出力例 3

3

問題文

縦に r 個、横に c 個の r×c 個のマスからなるグリッドがあり、それぞれのマスには * か . が書かれています。上から i 番目、左から j 番目のマスに書かれた文字を C_{i,j} とおきます。

kenkooooさんは . のマスにSoundHoundの広告を打つことにしました。1 つのマスには 1 個だけ広告を打てます。しかし、あまりに密集していると逆効果なので、隣り合う 2 つのマスの両方に広告を打つことはありません。ここで、隣り合う 2 つのマスとは、あるマスとその上下左右で隣り合うマスのことを表します。

kenkooooさんは最大でいくつ広告を打てるでしょうか？

制約

• 1≦r, c≦40
• C_{i,j} は . または * からなる

入力例 1

3 3
...
...
...

出力例 1

5

広告を打つマスを # で表すことにすると、以下のように 5 つの広告を打つことができます。

#.#
.#.
#.#

入力例 2

2 2
**
**

出力例 2

0

残念ながら、1 つも広告を打てないときもあります。

入力例 3

1 1
.

出力例 3

1

入力例 4

3 4
*..*
..**
*...

出力例 4

4

問題文

kenkooooさんはSoundHound社で働いています。建物は H 階建てで、1 つのフロアは W 個の東西に直線上につながった部屋からなります。上から i 番目の階の、西から j 番目の部屋を部屋 (i,j) と呼ぶことにします。

いま、kenkooooさんは部屋 (1,1) にいます。kenkooooさんは以下の動作を繰り返すことで、地上階(上から H 番目の階)の部屋から建物を出ることにしました:

• 部屋 (i,j) にいるとき、存在するなら部屋 (i,j-1)に移動する。
• 部屋 (i,j) にいるとき、存在するなら部屋 (i,j+1)に移動する。
• 部屋 (i,j) にいるとき、存在するなら部屋 (i+1,j)に移動する。

ただし、地上階にたどり着いてからも移動をしてもかまいません。

さらに、部屋 (i,j) には P_{i,j} 円が落ちており、その部屋に初めて入るときkenkooooさんはこれを拾います。

一方で、部屋 (i,j) に入るたびに、入室料として F_{i,j} 円を払う必要があります。

kenkooooさんはすでに十分大きい金額を今持っているため、途中で手持ちのお金がなくなってしまうことはありません。部屋 (H,j) から建物を出るとき、この建物で最大いくら得ることができるかをすべての 1≦j≦W について求めてください。

制約

• 2≦H≦10
• 1≦W≦5×10^4
• 0≦P_{i,j}<10^5
• 0≦F_{i,j}<10^5

入力例 1

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

出力例 1

0
5
2
7

例えば、部屋 (2,1) にたどり着くには、(1,1),(1,2),(1,3),(1,2),(2,2),(2,1) の順に訪れることで、2+1+3+3 円を手にしつつ、2+2+5 円を払うことで合計 0 円の利益を得ることができます。

入力例 2

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

出力例 2

6
6
6
-1

部屋 (1,1) でも入室料を取られること、地上にたどり着いた後も動いてよいこと、最終的な利益が負になることもあることに注意してください。

入力例 3

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

出力例 3

2
4
3
2

問題文

長さ m の文字列について、これが対応付いているとは、文字列が( と )からなり、(と)の数が等しく、どの i(≦m) についても、先頭 i 文字目までで(の数が)の数以上であるということを指します。例えば、(())や()(()())は対応付いた文字列で、)(や())、abcなどは対応付いた文字列ではありません。

対応付いた文字列について、そのスコアを)の添字の総和から、(の添字の総和を引いたものとして定義します。添字とは、その文字が左から何文字目に位置するかを表す整数です。例えば、(())についてスコアは 4 であり、()(()()) についてスコアは 8 です。

文字列の部分列とは、文字列からいくつかの文字を削除したのち、残った文字列の順番を変えずにつなげたものを指します。例えば、())について、空文字列、 ())や()は部分列ですが、)(は部分列ではありません。

はじめ、あなたは長さ N の文字列 S を持っています。以下のクエリーを Q 回処理するプログラムを書いてください。

• i番目のクエリーは、整数 k_i が与えられる。
• S の k_i 番目の文字を逆にする。すなわち、 ( なら ) にし、) なら ( にする。
• 編集後、S から取れる対応付いた部分列のスコアのうち、最大値を答えよ。

制約

• 1≦N, Q≦10^5
• S は ( と ) のみからなる
• 1≦k_i≦N

入力例 1

5 4
()(()
5
2
5
4

出力例 1

1
0
1
4

クエリーにより、文字列は

• ()(((
• (((((
• (((()
• ((())

と変化します。各文字列で取れる最大のスコアの部分列は、それぞれ

• ()
• (空文字列)
• ()
• (())

です。

入力例 2

5 3
(()))
2
1
5

出力例 2

1
0
0

入力例 3

6 6
())()(
3
4
1
5
6
2

出力例 3

2
4
1
1
2
4