Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は黒いマスと透明なマスからなるシート A,B を 1 枚ずつと、透明なマスのみからなる無限に広がるシート C を持っています。
また、高橋君には黒いマスと透明なマスからなる、理想とするシート X が存在します。
シート A,B,X の大きさはそれぞれ縦 H_A マス \times 横 W_A マス、縦 H_B マス \times 横 W_B マス、縦 H_X マス \times 横 W_X マスです。
シート A の各マスは . と # からなる長さ W_A の文字列 H_A 個 A_1,A_2,\ldots,A_{H_A} によって表され、
A_i (1\leq i\leq H_A) の j 文字目 (1\leq j\leq W_A) が、
. のときシート A の上から i 行目かつ左から j 列目のマスは透明なマスであり、
# のとき黒いマスです。
シート B,X の各マスも、同様に長さ W_B の文字列 H_B 個 B_1,B_2,\ldots,B_{H_B} および長さ W_X の文字列 H_X 個 X_1,X_2,\ldots,X_{H_X} によって表されます。
高橋君の目標は、次の手順で、シート A,B,C から、A,B に存在する すべての黒いマスを使って シート X を作り出すことです。
- シート A,B をマス目に沿ってシート C に貼り付ける。この時、シート A,B はそれぞれ好きな場所に平行移動させて貼って良いが、シートを切り分けたり、回転させたりしてはいけない。
- シート C からマス目に沿って H_X\times W_X マスの領域を切り出す。ここで、切り出されたシートの各マスは、シート A または B の黒いマスが貼り付けられていれば黒いマスに、そうでなければ透明なマスとなる。
このとき、貼り付ける位置と切り出す領域をうまくとることで高橋君は目標を達成できるか、すなわち次の条件をともにみたすことにできるか判定してください。
- 切り出されたシートはシート A,B の 黒いマスをすべて 含む。切り出されたシートの上でシート A,B の黒いマスどうしが重なって存在していても構わない。
- 切り出されたシートは、回転させたり裏返したりすることなくシート X と一致する。
制約
- 1\leq H_A,W_A,H_B,W_B,H_X,W_X\leq 10
- H_A,W_A,H_B,W_B,H_X,W_X は整数
- A_i は
.と#のみからなる長さ W_A の文字列 - B_i は
.と#のみからなる長さ W_B の文字列 - X_i は
.と#のみからなる長さ W_X の文字列 - シート A,B,X はそれぞれ少なくとも 1 つ以上の黒いマスを含む。
入力
入力は以下の形式で標準入力から与えられる。
H_A W_A
A_1
A_2
\vdots
A_{H_A}
H_B W_B
B_1
B_2
\vdots
B_{H_B}
H_X W_X
X_1
X_2
\vdots
X_{H_X}
出力
高橋君が問題文中の目標を達成できるならば Yes を、できないならば No を出力せよ。
入力例 1
3 5 #.#.. ..... .#... 2 2 #. .# 5 3 ... #.# .#. .#. ...
出力例 1
Yes
まず、シート A をシート C に貼り付けると下図のようになります。
\vdots
.......
.#.#...
\cdots.......\cdots
..#....
.......
\vdots
さらに、シート B をシート A と左上を合わせて貼ってみると下図のようになります。
\vdots
.......
.#.#...
\cdots..#....\cdots
..#....
.......
\vdots
ここで、上で具体的に図示されている範囲のうち、上から 1 行目かつ左から 2 列目のマスを左上として 5\times 3 マスを切り出すと下図のようになります。
... #.# .#. .#. ...
これはシート A,B のすべての黒いマスを含んでおり、また、シート X と一致しているため条件を満たしています。
よって、Yes を出力します。
入力例 2
2 2 #. .# 2 2 #. .# 2 2 ## ##
出力例 2
No
シート A や B を回転させて貼ってはいけないことに注意してください。
入力例 3
1 1 # 1 2 ## 1 1 #
出力例 3
No
どのように貼ったり切り出したりしても、シート B の黒いマスをすべて含むように切り出すことはできないため、1 つめの条件をみたすことができません。
よって、No を出力します。
入力例 4
3 3 ### ... ... 3 3 #.. #.. #.. 3 3 ..# ..# ###
出力例 4
Yes
Score : 300 points
Problem Statement
Takahashi has two sheets A and B, each composed of black squares and transparent squares, and an infinitely large sheet C composed of transparent squares.
There is also an ideal sheet X for Takahashi composed of black squares and transparent squares.
The sizes of sheets A, B, and X are H_A rows \times W_A columns, H_B rows \times W_B columns, and H_X rows \times W_X columns, respectively.
The squares of sheet A are represented by H_A strings of length W_A, A_1, A_2, \ldots, A_{H_A} consisting of . and #.
If the j-th character (1\leq j\leq W_A) of A_i (1\leq i\leq H_A) is ., the square at the i-th row from the top and j-th column from the left is transparent; if it is #, that square is black.
Similarly, the squares of sheets B and X are represented by H_B strings of length W_B, B_1, B_2, \ldots, B_{H_B}, and H_X strings of length W_X, X_1, X_2, \ldots, X_{H_X}, respectively.
Takahashi's goal is to create sheet X using all black squares in sheets A and B by following the steps below with sheets A, B, and C.
- Paste sheets A and B onto sheet C along the grid. Each sheet can be pasted anywhere by translating it, but it cannot be cut or rotated.
- Cut out an H_X\times W_X area from sheet C along the grid. Here, a square of the cut-out sheet will be black if a black square of sheet A or B is pasted there, and transparent otherwise.
Determine whether Takahashi can achieve his goal by appropriately choosing the positions where the sheets are pasted and the area to cut out, that is, whether he can satisfy both of the following conditions.
- The cut-out sheet includes all black squares of sheets A and B. The black squares of sheets A and B may overlap on the cut-out sheet.
- The cut-out sheet coincides sheet X without rotating or flipping.
Constraints
- 1\leq H_A, W_A, H_B, W_B, H_X, W_X\leq 10
- H_A, W_A, H_B, W_B, H_X, W_X are integers.
- A_i is a string of length W_A consisting of
.and#. - B_i is a string of length W_B consisting of
.and#. - X_i is a string of length W_X consisting of
.and#. - Sheets A, B, and X each contain at least one black square.
Input
The input is given from Standard Input in the following format:
H_A W_A
A_1
A_2
\vdots
A_{H_A}
H_B W_B
B_1
B_2
\vdots
B_{H_B}
H_X W_X
X_1
X_2
\vdots
X_{H_X}
Output
If Takahashi can achieve the goal described in the problem statement, print Yes; otherwise, print No.
Sample Input 1
3 5 #.#.. ..... .#... 2 2 #. .# 5 3 ... #.# .#. .#. ...
Sample Output 1
Yes
First, paste sheet A onto sheet C, as shown in the figure below.
\vdots
.......
.#.#...
\cdots.......\cdots
..#....
.......
\vdots
Next, paste sheet B so that its top-left corner aligns with that of sheet A, as shown in the figure below.
\vdots
.......
.#.#...
\cdots..#....\cdots
..#....
.......
\vdots
Now, cut out a 5\times 3 area with the square in the first row and second column of the range illustrated above as the top-left corner, as shown in the figure below.
... #.# .#. .#. ...
This includes all black squares of sheets A and B and matches sheet X, satisfying the conditions.
Therefore, print Yes.
Sample Input 2
2 2 #. .# 2 2 #. .# 2 2 ## ##
Sample Output 2
No
Note that sheets A and B may not be rotated or flipped when pasting them.
Sample Input 3
1 1 # 1 2 ## 1 1 #
Sample Output 3
No
No matter how you paste or cut, you cannot cut out a sheet that includes all black squares of sheet B, so you cannot satisfy the first condition.
Therefore, print No.
Sample Input 4
3 3 ### ... ... 3 3 #.. #.. #.. 3 3 ..# ..# ###
Sample Output 4
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
高橋君は医者のすぬけ君から N 種類の薬を処方されました。i 種類目の薬は(処方された日を含めて) a_i 日間、毎日 b_i 錠ずつ飲む必要があります。また、高橋君はこれ以外の薬を飲む必要がありません。
薬を処方された日を 1 日目とします。1 日目以降で、初めて高橋君がその日に飲む必要がある薬が K 錠以下になるのは何日目かを求めてください。
制約
- 1 \leq N \leq 3 \times 10^5
- 0 \leq K \leq 10^9
- 1 \leq a_i,b_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K a_1 b_1 \vdots a_N b_N
出力
1 日目以降で、初めて高橋君がその日に飲む必要がある薬が K 錠以下になるのが X 日目の時、 X を出力せよ。
入力例 1
4 8 6 3 2 5 1 9 4 2
出力例 1
3
1 日目には、高橋君は 1,2,3,4 種類目の薬をそれぞれ 3,5,9,2 錠飲む必要があります。よってこの日は 19 錠飲む必要があり、K(=8) 錠以下ではありません。
2 日目には、高橋君は 1,2,4 種類目の薬をそれぞれ 3,5,2 錠飲む必要があります。よってこの日は 10 錠飲む必要があり、K(=8) 錠以下ではありません。
3 日目には、高橋君は 1,4 種類目の薬をそれぞれ 3,2 錠飲む必要があります。よってこの日は 5 錠飲む必要があり、初めて K(=8) 錠以下になります。
以上より、3 が答えです。
入力例 2
4 100 6 3 2 5 1 9 4 2
出力例 2
1
入力例 3
15 158260522 877914575 2436426 24979445 61648772 623690081 33933447 476190629 62703497 211047202 71407775 628894325 31963982 822804784 50968417 430302156 82631932 161735902 80895728 923078537 7723857 189330739 10286918 802329211 4539679 303238506 17063340 492686568 73361868 125660016 50287940
出力例 3
492686569
Score : 350 points
Problem Statement
Snuke the doctor prescribed N kinds of medicine for Takahashi. For the next a_i days (including the day of the prescription), he has to take b_i pills of the i-th medicine. He does not have to take any other medicine.
Let the day of the prescription be day 1. On or after day 1, when is the first day on which he has to take K pills or less?
Constraints
- 1 \leq N \leq 3 \times 10^5
- 0 \leq K \leq 10^9
- 1 \leq a_i,b_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K a_1 b_1 \vdots a_N b_N
Output
If Takahashi has to take K pills or less on day X for the first time on or after day 1, print X.
Sample Input 1
4 8 6 3 2 5 1 9 4 2
Sample Output 1
3
On day 1, he has to take 3,5,9, and 2 pills of the 1-st, 2-nd, 3-rd, and 4-th medicine, respectively. In total, he has to take 19 pills on this day, which is not K(=8) pills or less.
On day 2, he has to take 3,5, and 2 pills of the 1-st, 2-nd, and 4-th medicine, respectively. In total, he has to take 10 pills on this day, which is not K(=8) pills or less.
On day 3, he has to take 3 and 2 pills of the 1-st and 4-th medicine, respectively. In total, he has to take 5 pills on this day, which is K(=8) pills or less for the first time.
Thus, the answer is 3.
Sample Input 2
4 100 6 3 2 5 1 9 4 2
Sample Output 2
1
Sample Input 3
15 158260522 877914575 2436426 24979445 61648772 623690081 33933447 476190629 62703497 211047202 71407775 628894325 31963982 822804784 50968417 430302156 82631932 161735902 80895728 923078537 7723857 189330739 10286918 802329211 4539679 303238506 17063340 492686568 73361868 125660016 50287940
Sample Output 3
492686569
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
空の筒があります。Q 個のクエリが与えられるので順に処理してください。
クエリは次の 2 種類のいずれかです。
1 x c:数 x が書かれたボールを筒の右側から c 個入れる2 c:筒の左側からボールを c 個取り出し、取り出したボールに書かれている数の合計を出力する
なお、筒の中でボールの順序が入れ替わることはないものとします。
制約
- 1 \leq Q \leq 2\times 10^5
- 0 \leq x \leq 10^9
- 1 \leq c \leq 10^9
2 cのクエリが与えられるとき、筒の中には c 個以上のボールがある- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
Q
{\rm query}_1
\vdots
{\rm query}_Q
i 番目のクエリを表す {\rm query}_i は以下の 2 種類のいずれかである。
1 x c
2 c
出力
2 c のクエリに対する答えを順に改行区切りで出力せよ。
入力例 1
4 1 2 3 2 2 1 3 4 2 3
出力例 1
4 8
- 1 番目のクエリでは、2 が書かれたボールを筒の右側から 3 個入れます。
筒の中のボールに書かれた数は左から順に (2,2,2) となります。 - 2 番目のクエリでは、筒の左側からボールを 2 個取り出します。
取り出されたボールに書かれている数はそれぞれ 2,2 であり、合計は 4 であるため、これを出力します。 筒の中のボールに書かれた数は左から順に (2) となります。 - 3 番目のクエリでは、3 が書かれたボールを筒の右側から 4 個入れます。
筒の中のボールに書かれた数は左から順に (2,3,3,3,3) となります。 - 4 番目のクエリでは、筒の左側からボールを 3 個取り出します。
取り出されたボールに書かれている数はそれぞれ 2,3,3 であり、合計は 8 であるため、これを出力します。 筒の中のボールに書かれた数は左から順に (3,3) となります。
入力例 2
2 1 1000000000 1000000000 2 1000000000
出力例 2
1000000000000000000
入力例 3
5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
出力例 3
出力するものがないこともあります。
Score : 400 points
Problem Statement
We have a horizontal cylinder. Given Q queries, process them in the given order.
Each query is of one of the following two types.
1 x c: Insert c balls, with a number x written on each of them, to the right end of the cylinder.2 c: Take out the c leftmost balls contained in the cylinder and print the sum of the numbers written on the balls that have been taken out.
We assume that the balls do never change their order in the cylinder.
Constraints
- 1 \leq Q \leq 2\times 10^5
- 0 \leq x \leq 10^9
- 1 \leq c \leq 10^9
- Whenever a query of type
2 cis given, there are c or more balls in the cylinder. - All values in input are integers.
Input
Input is given from Standard Input in the following format:
Q
{\rm query}_1
\vdots
{\rm query}_Q
The i-th query {\rm query}_i is in one of the following two formats.
1 x c
2 c
Output
Print the response to the queries of type 2 c in the given order, with newlines in between.
Sample Input 1
4 1 2 3 2 2 1 3 4 2 3
Sample Output 1
4 8
- For the 1-st query, insert 3 balls, with a number 2 written on each of them, to the right end of the cylinder.
The cylinder has now balls with numbers (2,2,2) written on them, from left to right. - For the 2-nd query, take out the 2 leftmost balls contained in the cylinder.
The numbers written on the balls taken out are 2,2, for a sum of 4, which should be printed. The cylinder has now a ball with a number (2) written on it, from left to right. - For the 3-rd query, insert 4 balls, with a number 3 written on each of them, to the right end of the cylinder.
The cylinder has now balls with numbers (2,3,3,3,3) written on them, from left to right. - For the 4-th query, take out the 3 leftmost balls contained in the cylinder.
The numbers written on the balls taken out are 2,3,3, for a sum of 8, which should be printed. The cylinder has now balls with numbers (3,3) written on them, from left to right.
Sample Input 2
2 1 1000000000 1000000000 2 1000000000
Sample Output 2
1000000000000000000
Sample Input 3
5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Sample Output 3
There may be nothing you should print.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
数列 X に対し、 f(X) = ( X を回文にするために変更する必要のある要素の個数の最小値 ) とします。
与えられた長さ N の数列 A の全ての 連続 部分列 X に対する f(X) の総和を求めてください。
但し、長さ m の数列 X が回文であるとは、全ての 1 \le i \le m を満たす整数 i について、 X の i 項目と m+1-i 項目が等しいことを指します。
制約
- 入力は全て整数
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le N
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
5 5 2 1 2 2
出力例 1
9
- f(5) = 0
- f(2) = 0
- f(1) = 0
- f(2) = 0
- f(2) = 0
- f(5,2) = 1
- f(2,1) = 1
- f(1,2) = 1
- f(2,2) = 0
- f(5,2,1) = 1
- f(2,1,2) = 0
- f(1,2,2) = 1
- f(5,2,1,2) = 2
- f(2,1,2,2) = 1
- f(5,2,1,2,2) = 1
以上より、求める答えは 9 です。
Score : 500 points
Problem Statement
For a sequence X, let f(X) = (the minimum number of elements one must modify to make X a palindrome).
Given a sequence A of length N, find the sum of f(X) over all contiguous subarrays of A.
Here, a sequence X of length m is said to be a palindrome if and only if the i-th and the (m+1-i)-th elements of X are equal for all 1 \le i \le m.
Constraints
- All values in the input are integers.
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le N
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
5 5 2 1 2 2
Sample Output 1
9
- f(5) = 0
- f(2) = 0
- f(1) = 0
- f(2) = 0
- f(2) = 0
- f(5,2) = 1
- f(2,1) = 1
- f(1,2) = 1
- f(2,2) = 0
- f(5,2,1) = 1
- f(2,1,2) = 0
- f(1,2,2) = 1
- f(5,2,1,2) = 2
- f(2,1,2,2) = 1
- f(5,2,1,2,2) = 1
Therefore, the sought answer is 9.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
英大小文字と ( 、 ) からなる文字列 S=S_1 S_2 S_3 \dots S_{|S|} が与えられます。
文字列 S 中の括弧は、対応が取れています。
次の操作を、操作ができなくなるまで繰り返します。
- まず、以下の条件を全て満たす整数組 (l,r) をひとつ選択する。
- l < r
- S_l =
( - S_r =
) - S_{l+1},S_{l+2},\dots,S_{r-1} は全て英大文字または英小文字である
- T=\overline{S_{r-1}S_{r-2} \dots S_{l+1}} とする。
- 但し、 \overline{x} は x の大文字と小文字を反転させた文字列を指す。
- その後、 S の l 文字目から r 文字目までを削除し、削除した位置に T を挿入する。
詳細は入出力例を参照してください。
上記の操作を使って全ての ( と ) を除去することができ、最終的な文字列は操作の方法や順序によらないことが証明できます。
このとき、最終的な文字列を求めてください。
「 S 中の括弧の対応が取れている」とは?
まず、正しい括弧列を次の通り定義します。- 正しい括弧列とは、以下のいずれかの条件を満たす文字列です。
- 空文字列
- ある正しい括弧列 A が存在して、
(, A,)をこの順に連結した文字列 - ある空でない正しい括弧列 A,B が存在して、 A,B をこの順に連結した文字列
( と ) を順序を保って抜き出した時、それが正しい括弧列となることを指す。
制約
- 1 \le |S| \le 5 \times 10^5
- S は英大小文字と
(、)からなる - S 中の括弧は対応が取れている
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
((A)y)x
出力例 1
YAx
S= ((A)y)x に対して操作を行います。
- l=2,r=4 を選択します。このとき削除される文字列は
(A)で、代わりにaが挿入されます。- この操作の結果、 S=
(ay)xとなります。
- この操作の結果、 S=
- l=1,r=4 を選択します。このとき削除される文字列は
(ay)で、代わりにYAが挿入されます。- この操作の結果、 S=
YAxとなります。
- この操作の結果、 S=
括弧を除去した結果、文字列は YAx となったので、これを出力してください。
入力例 2
((XYZ)n(X(y)Z))
出力例 2
XYZNXYZ
S= ((XYZ)n(X(y)Z)) に対して操作を行います。
- l=10,r=12 を選択します。このとき削除される文字列は
(y)で、代わりにYが挿入されます。- この操作の結果、 S=
((XYZ)n(XYZ))となります。
- この操作の結果、 S=
- l=2,r=6 を選択します。このとき削除される文字列は
(XYZ)で、代わりにzyxが挿入されます。- この操作の結果、 S=
(zyxn(XYZ))となります。
- この操作の結果、 S=
- l=6,r=10 を選択します。このとき削除される文字列は
(XYZ)で、代わりにzyxが挿入されます。- この操作の結果、 S=
(zyxnzyx)となります。
- この操作の結果、 S=
- l=1,r=9 を選択します。このとき削除される文字列は
(zyxnzyx)で、代わりにXYZNXYZが挿入されます。- この操作の結果、 S=
XYZNXYZとなります。
- この操作の結果、 S=
括弧を除去した結果、文字列は XYZNXYZ となったので、これを出力してください。
入力例 3
(((()))(()))(())
出力例 3
操作結果が空文字列になる場合もあります。
入力例 4
dF(qT(plC())NnnfR(GsdccC))PO()KjsiI((ysA)eWW)ve
出力例 4
dFGsdccCrFNNnplCtQPOKjsiIwwEysAve
Score: 550 points
Problem Statement
You are given a string S = S_1 S_2 S_3 \dots S_{|S|} consisting of uppercase and lowercase English letters, (, and ).
The parentheses in the string S are properly matched.
Repeat the following operation until no more operations can be performed:
- First, select one pair of integers (l, r) that satisfies all of the following conditions:
- l < r
- S_l =
( - S_r =
) - Each of the characters S_{l+1}, S_{l+2}, \dots, S_{r-1} is an uppercase or lowercase English letter.
- Let T = \overline{S_{r-1} S_{r-2} \dots S_{l+1}}.
- Here, \overline{x} denotes the string obtained by toggling the case of each character in x (uppercase to lowercase and vice versa).
- Then, delete the l-th through r-th characters of S and insert T at the position where the deletion occurred.
Refer to the sample inputs and outputs for clarification.
It can be proved that it is possible to remove all (s and )s from the string using the above operations, and the final string is independent of how and in what order the operations are performed.
Determine the final string.
What does it mean that the parentheses in S are properly matched?
First, a correct parenthesis sequence is defined as follows:- A correct parenthesis sequence is a string that satisfies one of the following conditions:
- It is an empty string.
- There exists a correct parenthesis sequence A, and the string is formed by concatenating
(, A,)in this order. - There exist non-empty correct parenthesis sequences A and B, and the string is formed by concatenating A and B in this order.
(s and )s extracted from S without changing the order form a correct parenthesis sequence.
Constraints
- 1 \le |S| \le 5 \times 10^5
- S consists of uppercase and lowercase English letters,
(, and). - The parentheses in S are properly matched.
Input
The input is given from Standard Input in the following format:
S
Output
Print the final string.
Sample Input 1
((A)y)x
Sample Output 1
YAx
Let us perform the operations for S = ((A)y)x.
- Choose l=2 and r=4. The substring
(A)is removed and replaced witha.- After this operation, S =
(ay)x.
- After this operation, S =
- Choose l=1 and r=4. The substring
(ay)is removed and replaced withYA.- After this operation, S =
YAx.
- After this operation, S =
After removing the parentheses, the string becomes YAx, which should be printed.
Sample Input 2
((XYZ)n(X(y)Z))
Sample Output 2
XYZNXYZ
Let us perform the operations for S = ((XYZ)n(X(y)Z)).
- Choose l=10 and r=12. The substring
(y)is removed and replaced withY.- After this operation, S =
((XYZ)n(XYZ)).
- After this operation, S =
- Choose l=2 and r=6. The substring
(XYZ)is removed and replaced withzyx.- After this operation, S =
(zyxn(XYZ)).
- After this operation, S =
- Choose l=6 and r=10. The substring
(XYZ)is removed and replaced withzyx.- After this operation, S =
(zyxnzyx).
- After this operation, S =
- Choose l=1 and r=9. The substring
(zyxnzyx)is removed and replaced withXYZNXYZ.- After this operation, S =
XYZNXYZ.
- After this operation, S =
After removing the parentheses, the string becomes XYZNXYZ, which should be printed.
Sample Input 3
(((()))(()))(())
Sample Output 3
The final outcome may be an empty string.
Sample Input 4
dF(qT(plC())NnnfR(GsdccC))PO()KjsiI((ysA)eWW)ve
Sample Output 4
dFGsdccCrFNNnplCtQPOKjsiIwwEysAve