A - Exchange

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

日本では、1 円、5 円、10 円、50 円、100 円、500 円の 6 種類の硬貨が流通しています。これについて、次の問いに答えてください。

AtCoder さんの財布の中には、1 円硬貨 A 枚、5 円硬貨 B 枚、10 円硬貨 C 枚、50 円硬貨 D 枚、100 円硬貨 E 枚、500 円硬貨 F 枚が入っています。

AtCoder さんは、これから N 個の店で順番に買い物を行います。 具体的には、i 番目 (1 \leq i \leq N) に訪れる店では税込 X_i 円の商品を 1 つ購入する予定です。

釣銭の授受には時間がかかるので、彼は支払いに使う硬貨を上手く選ぶことで、すべての店でちょうどの金額を支払って商品を購入したいです。 このようなことが可能か、判定してください。

制約

  • 0 \leq A \leq 200
  • 0 \leq B \leq 200
  • 0 \leq C \leq 200
  • 0 \leq D \leq 200
  • 0 \leq E \leq 200
  • 0 \leq F \leq 200
  • 1 \leq N \leq 10
  • 1 \leq X_i \leq 10000 \ (1 \leq i \leq N)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。 

A B C D E F
N
X_1 X_2 \cdots X_N

出力

可能ならば Yes、不可能ならば No と出力してください。

入力例 1

0 0 6 3 4 1
3
700 250 160

出力例 1

Yes

たとえば以下のように支払いを行うと、3 店舗すべてでちょうどの支払いを行うことができます。

  • 1 番目に訪れる店：100 円硬貨を 2 枚、500 円硬貨を 1 枚使う。
  • 2 番目に訪れる店：10 円硬貨を 5 枚、100 円硬貨を 2 枚使う。
  • 3 番目に訪れる店：10 円硬貨を 1 枚、50 円硬貨を 3 枚使う。

入力例 2

0 0 0 2 4 0
3
100 200 300

出力例 2

No

財布に入っている金額は 500 円ですが、合計 100+200+300=600 円の支払いを行う必要があるため、すべての商品を購入することができません。

入力例 3

0 0 0 0 8 8
1
250

出力例 3

No

財布に 50 円以下の硬貨が入っていないため、250 円ちょうどを支払うことはできません。

入力例 4

20 5 9 7 10 6
5
177 177 177 177 177

出力例 4

Yes

入力例 5

17 5 9 7 10 6
5
177 177 177 177 177

出力例 5

No

Score: 300 points

Problem Statement

In Japan, there are six types of coins in circulation: 1 yen, 5 yen, 10 yen, 50 yen, 100 yen, and 500 yen. Answer the following question regarding these coins.

Mr. AtCoder's wallet contains A 1-yen coins, B 5-yen coins, C 10-yen coins, D 50-yen coins, E 100-yen coins, and F 500-yen coins.

He is planning to shop at N stores in sequence. Specifically, at the i-th store (1 \leq i \leq N), he plans to buy one item that costs X_i yen (including tax).

Giving and receiving change takes time, so he wants to choose his coins so that he can pay the exact amount at each store. Determine if this is possible.

Constraints

  • 0 \leq A \leq 200
  • 0 \leq B \leq 200
  • 0 \leq C \leq 200
  • 0 \leq D \leq 200
  • 0 \leq E \leq 200
  • 0 \leq F \leq 200
  • 1 \leq N \leq 10
  • 1 \leq X_i \leq 10000 \ (1 \leq i \leq N)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

A B C D E F
N
X_1 X_2 \cdots X_N

Output

Print Yes if the objective is achievable, and No otherwise.

Sample Input 1

0 0 6 3 4 1
3
700 250 160

Sample Output 1

Yes

For example, he can make exact payments at all three stores as follows:

  • At the first store: Use two 100-yen coins and one 500-yen coin.
  • At the second store: Use five 10-yen coins and two 100-yen coins.
  • At the third store: Use one 10-yen coin and three 50-yen coins.

Sample Input 2

0 0 0 2 4 0
3
100 200 300

Sample Output 2

No

The total amount in the wallet is 500 yen, but a total payment of 100+200+300=600 yen is required, so it is impossible to purchase all the items.

Sample Input 3

0 0 0 0 8 8
1
250

Sample Output 3

No

There are no 50-yen or smaller coins in the wallet, so it is impossible to pay exactly 250 yen.

Sample Input 4

20 5 9 7 10 6
5
177 177 177 177 177

Sample Output 4

Yes

Sample Input 5

17 5 9 7 10 6
5
177 177 177 177 177

Sample Output 5

No
B - Puzzle of Lamps

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

AtCoder さんは、左から右へ一列に並べられた N 個の豆電球と、2 種類のスイッチ A, B で構成された装置を作りました。各豆電球は、0 (OFF) と 1 (ON) の 2 種類の状態をとります。各スイッチを押すと、以下のことが起こります。

  • スイッチ A を押すと、0 の状態の豆電球のうち一番左のものが 1 になる。
  • スイッチ B を押すと、1 の状態の豆電球のうち一番左のものが 0 になる。

なお、該当する豆電球が存在しない場合はスイッチを押せません。

最初、すべての豆電球は 0 の状態になっています。AtCoder さんは、左の豆電球から順に状態が S_1, S_2, \dots, S_N になっている状態にしたいです。そのためにスイッチをどの順番で何回押せばいいのかを答えてください。ここで、必ずしもスイッチを押す回数を最小化する必要はありませんが、操作を現実的な時間で終わらせるために、スイッチを押す回数は 10^6 回以下にしてください。なお、この問題の制約下では、答えが存在することが証明できます。

制約

  • 1 \leq N \leq 30
  • S_1, S_2, \dots, S_N は 0 または 1
  • S_1, S_2, \dots, S_N がすべて 0 であることはない
  • N は整数

入力

入力は以下の形式で標準入力から与えられます。 

N
S_1 S_2 \dots S_N

入力の 2 行目は長さ N の文字列として与えられることに注意してください。

出力

答えたい操作方法が、スイッチを m 回 (1 \leq m \leq 10^6)、スイッチ t_1, t_2, \dots, t_m（すべて A または B）の順番で押すものである場合、以下の形式で出力してください。

m
t_1 t_2 \dots t_m

出力の 2 行目は長さ m の文字列として出力してください。

入力例 1

5
01100

出力例 1

4
AAAB

この出力例で答えているのは、スイッチ A, A, A, B の順に押す操作方法です。以下の図のように、豆電球を目的の状態にすることができます。

別の方法として、スイッチ A, A, B, A, A, B の順に押しても、豆電球を目的の状態にすることができます。これに対応する以下の出力をした場合でも正解になります。

6
AABAAB

Score: 400 points

Problem Statement

Mr. AtCoder has created a device consisting of N small light bulbs arranged in a row from left to right, and two switches A and B. Each light bulb can be in one of two states: 0 (OFF) and 1 (ON). Pressing each switch causes the following:

  • Pressing switch A turns the leftmost light bulb in the 0 state into 1.
  • Pressing switch B turns the leftmost light bulb in the 1 state into 0.

If there is no applicable light bulb, you cannot press the switch.

Initially, all light bulbs are in the 0 state. He wants the states of the light bulbs to be S_1, S_2, \dots, S_N from left to right. Determine the order and number of times the switches should be pressed to achieve this. It is not necessary to minimize the number of presses, but it should be at most 10^6 so that the operations can finish in a realistic time. It can be proved that a solution exists under the constraints of this problem.

Constraints

  • 1 \leq N \leq 30
  • Each of S_1, S_2, \dots, S_N is 0 or 1.
  • Not all of S_1, S_2, \dots, S_N are 0.
  • N is an integer.

Input

The input is given from Standard Input in the following format:

N
S_1 S_2 \dots S_N

Note that the second line is given as a string of length N.

Output

If your solution presses the switches m times (1 \leq m \leq 10^6) in the order t_1, t_2, \dots, t_m (each being A or B), print those in the following format:

m
t_1 t_2 \dots t_m

The second line should be printed as a string of length m.

Sample Input 1

5
01100

Sample Output 1

4
AAAB

This sample output presents a solution that presses the switches in the order A, A, A, B. This sets the light bulbs to the desired states, as shown in the figure below:

Alternatively, pressing switches in the order A, A, B, A, A, B also sets the light bulbs to the desired states. The following output corresponding to this solution would also be accepted:

6
AABAAB
C - Routing

実行時間制限: 2.5 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

N 行 N 列のマス目があり、上から i (1 \leq i \leq N) 行目・左から j 列目 (1 \leq j \leq N) のマスを (i, j) と表します。 各マスは最初赤色か青色で塗られており、マス (i, j) は c_{i,j}=R のとき赤色で、c_{i,j}=B のとき青色で塗られています。 あなたは、いくつかのマスの色を紫色に変えることで、以下の 2 つの条件を同時に満たすようにしたいです。

条件1　赤色と紫色のマスのみを通って、マス (1, 1) からマス (N, N) に移動できる。
条件2　青色と紫色のマスのみを通って、マス (1, N) からマス (N, 1) に移動できる。

ただし、移動できるとは、該当する色のマスのみを通って上下左右に隣接するマスへの移動を繰り返すことで、 出発地点から到着地点までたどり着けることを指します。

条件を満たすには、最小で何個のマスを紫色に変えなければならないでしょうか。

制約

  • 3 \leq N \leq 500
  • c_{i,j} は R または B
  • c_{1,1} および c_{N,N} は R
  • c_{1,N} および c_{N,1} は B
  • N は整数

入力

入力は以下の形式で標準入力から与えられます。 

N
c_{1,1}c_{1,2}\cdotsc_{1,N}
c_{2,1}c_{2,2}\cdotsc_{2,N}
\vdots
c_{N,1}c_{N,2}\cdotsc_{N,N}

出力

答えを出力してください。

入力例 1

5
RBRBB
RBRRR
RRRBR
RBBRB
BBRBR

出力例 1

3

以下の図のように、マス (1, 3), (3, 2), (4, 5) の 3 個を紫色に変えると、条件を満たすようになります。

入力例 2

5
RBBBB
BBBBB
BBBBB
BBBBB
BBBBR

出力例 2

7

以下の図のように、マス (1, 2), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4), (4, 5) の 7 個を紫色に変えると、条件を満たすようになります。

入力例 3

10
RRBBBBBBBB
BRRBBBBBBB
BBRRBBBBBB
BBBRRBBBBB
BBBBRRBBBB
BBBBBRRBBB
BBBBBBRRBB
BBBBBBBRRB
BBBBBBBBRR
BBBBBBBBBR

出力例 3

2

入力例 4

17
RBBRRBRRRRRBBBBBB
BBRBRBRRBRRBRRBBR
BRBRBBBRBBRBBRBBB
RBRRBBBBBBRRBRRRR
RRRRRBRBRRRBBRBBR
RRRRRBRRBRBBRRRBB
BBBRRRBRBRBBRRRBB
BBRRRBRBBBRBRRRBR
RRBBBBBBBBBBBRBRR
RRRBRRBRBRBRBRBBB
RRBRRRRBRBRRBRBBR
RRRBBRBRBBBRBBRBR
BBRBBRRBRRRBBRBBB
BBBRBRRRRRRRBBRBB
RRRRRBRBRBBRRBRRR
BRRRRBBBRRRBRRBBB
BBRRBBRRRBBBRBBBR

出力例 4

8

Score: 500 points

Problem Statement

There is a grid with N rows and N columns. Let (i, j) (1 \leq i \leq N, 1 \leq j \leq N) denote the cell at the i-th row from the top and the j-th column from the left. Each cell is initially painted red or blue, with cell (i, j) being red if c_{i,j}=R and blue if c_{i,j}=B. You want to change the colors of some cells to purple so that the following two conditions are simultaneously satisfied:

Condition 1: You can move from cell (1, 1) to cell (N, N) by only passing through cells that are red or purple.
Condition 2: You can move from cell (1, N) to cell (N, 1) by only passing through cells that are blue or purple.

Here, "You can move" means that you can reach the destination from the starting point by repeatedly moving to a horizontally or vertically adjacent cell of the relevant colors.

What is the minimum number of cells that must be changed to purple to satisfy these conditions?

Constraints

  • 3 \leq N \leq 500
  • Each c_{i,j} is R or B.
  • c_{1,1} and c_{N,N} are R.
  • c_{1,N} and c_{N,1} are B.
  • N is an integer.

Input

The input is given from Standard Input in the following format:

N
c_{1,1}c_{1,2}\cdotsc_{1,N}
c_{2,1}c_{2,2}\cdotsc_{2,N}
\vdots
c_{N,1}c_{N,2}\cdotsc_{N,N}

Output

Print the answer.

Sample Input 1

5
RBRBB
RBRRR
RRRBR
RBBRB
BBRBR

Sample Output 1

3

As shown in the figure below, changing cells (1, 3), (3, 2), (4, 5) to purple satisfies the conditions.

Sample Input 2

5
RBBBB
BBBBB
BBBBB
BBBBB
BBBBR

Sample Output 2

7

As shown in the figure below, changing cells (1, 2), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4), (4, 5) to purple satisfies the conditions.

Sample Input 3

10
RRBBBBBBBB
BRRBBBBBBB
BBRRBBBBBB
BBBRRBBBBB
BBBBRRBBBB
BBBBBRRBBB
BBBBBBRRBB
BBBBBBBRRB
BBBBBBBBRR
BBBBBBBBBR

Sample Output 3

2

Sample Input 4

17
RBBRRBRRRRRBBBBBB
BBRBRBRRBRRBRRBBR
BRBRBBBRBBRBBRBBB
RBRRBBBBBBRRBRRRR
RRRRRBRBRRRBBRBBR
RRRRRBRRBRBBRRRBB
BBBRRRBRBRBBRRRBB
BBRRRBRBBBRBRRRBR
RRBBBBBBBBBBBRBRR
RRRBRRBRBRBRBRBBB
RRBRRRRBRBRRBRBBR
RRRBBRBRBBBRBBRBR
BBRBBRRBRRRBBRBBB
BBBRBRRRRRRRBBRBB
RRRRRBRBRBBRRBRRR
BRRRRBBBRRRBRRBBB
BBRRBBRRRBBBRBBBR

Sample Output 4

8
D - Earthquakes

実行時間制限: 2.5 sec / メモリ制限: 1024 MiB

配点 : 700 点

問題文

AtCoder 街道は、平らな地面の上に伸びる数直線で表される道路です。この道路上に N 個の高さ H の電柱が立っています。電柱には 1, 2, \dots, N の番号が古い順に付けられています。電柱 i \ (1 \leq i \leq N) は座標 X_i に地面と垂直に立っています。電柱の最下部は地面に固定されています。ここで、電柱は十分に細いものとして考えます。

AtCoder 街道ではこれから N 回の地震が発生します。i 回目 (1 \leq i \leq N) の地震では、以下のことが起こります。

  1. 電柱 i がまだ倒れていない場合、それが数直線における左または右の方向に、それぞれ \frac{1}{2} ずつの確率で倒れる。
  2. 倒れようとしている電柱が、まだ倒れていない電柱に衝突した場合（電柱の最下部に衝突した場合を含む）、この電柱も同じ方向に倒れる。場合によってはこれが連鎖的に起こる。

ここで、1. で電柱がどちら方向に倒れるかは、他の電柱がどちら方向に倒れたかに関係しません。

以下の図は一回の地震での電柱の倒れ方の一例です。

地震対策のため、t = 1, 2, \dots, N それぞれについて、ちょうど t 回目の地震ですべての電柱が倒れた状態になる確率を 2^N 倍した値を 998244353 で割った余りを求めてください。なお、出力すべき値は整数になることが証明できます。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq H \leq 10^9
  • 0 \leq X_i \leq 10^9 \ (1 \leq i \leq N)
  • X_1, X_2, \dots, X_N はすべて異なる
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。 

N H
X_1 X_2 \cdots X_N

出力

t = 1, 2, \dots, N についての答えをその順番で空白区切りで出力してください。

入力例 1

3 2
0 3 1

出力例 1

4 2 2

以下の図は、この入力例における電柱の倒れ方の可能性を示しています。図中の分数はその状態になる確率を示しています。

したがって、ちょうど 1, 2, 3 回目の地震ですべての電柱が倒れた状態になる確率は、それぞれ \frac{1}{2}, \frac{1}{4}, \frac{1}{4} です。これを 8 倍した 4, 2, 2 を出力しましょう。

入力例 2

4 10
10 55 20 45

出力例 2

0 4 4 8

以下の図は、この入力例における電柱の倒れ方の可能性を示しています。図中の分数はその状態になる確率を示しています。

したがって、ちょうど 1, 2, 3, 4 回目の地震ですべての電柱が倒れた状態になる確率は、それぞれ 0, \frac{1}{4}, \frac{1}{4}, \frac{1}{2} です。これを 16 倍した 0, 4, 4, 8 を出力しましょう。

入力例 3

8 1
5 0 6 3 8 1 7 2

出力例 3

0 64 32 48 24 28 28 32

ちょうど 1, 2, 3, 4, 5, 6, 7, 8 回目の地震ですべての電柱が倒れた状態になる確率は、それぞれ 0, \frac{1}{4}, \frac{1}{8}, \frac{3}{16}, \frac{3}{32}, \frac{7}{64}, \frac{7}{64}, \frac{1}{8} です。

入力例 4

40 20
695 793 11 502 114 861 559 4 212 609 894 435 429 94 91 258 161 45 33 605 673 634 629 163 283 826 409 84 507 548 31 248 588 340 357 168 926 949 322 912

出力例 4

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 41942627 41942627 360709869

37 回目の地震までにすべての電柱が倒れることはありません。ちょうど 38, 39, 40 回目の地震ですべての電柱が倒れた状態になる確率は、それぞれ \frac{3}{8}, \frac{3}{8}, \frac{1}{4} です。

Score: 700 points

Problem Statement

AtCoder Street is a road represented by a straight line on flat ground. There are N utility poles of height H standing on this road. The poles are numbered 1, 2, \dots, N in chronological order. Pole i (1 \leq i \leq N) is vertically positioned at coordinate X_i. The base of each pole is fixed to the ground. Assume that the poles are sufficiently thin.

The street will experience N earthquakes. During the i-th earthquake (1 \leq i \leq N), the following events occur:

  1. If pole i has not yet fallen, it falls to the left or the right on the number line, each with a probability of \frac{1}{2}.
  2. If a falling pole collides with another pole that has not yet fallen (including collision at the base of the pole), the latter pole will also fall in the same direction. This may trigger a chain reaction.

The direction in which a pole falls during step 1 is independent of the direction in which other poles have fallen.

The following figure is an example of how poles might fall during one earthquake:

For earthquake preparedness, for each t = 1, 2, \dots, N, find the probability that all poles have fallen by exactly the t-th earthquake. Multiply it by 2^N and print the result modulo 998244353. It can be proved that the values to be printed are integers.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq H \leq 10^9
  • 0 \leq X_i \leq 10^9 \ (1 \leq i \leq N)
  • X_1, X_2, \dots, X_N are all distinct.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N H
X_1 X_2 \cdots X_N

Output

Print the answers for t = 1, 2, \dots, N in this order, separated by spaces.

Sample Input 1

3 2
0 3 1

Sample Output 1

4 2 2

The following figure shows the possible ways the poles can fall for this sample input. The fractions in the figure indicate the probability of each state occurring.

Therefore, the probabilities that all poles have fallen by exactly the 1-st, 2-nd, 3-rd earthquakes are \frac{1}{2}, \frac{1}{4}, \frac{1}{4}, respectively. Multiply these by 8 to get 4, 2, 2 for output.

Sample Input 2

4 10
10 55 20 45

Sample Output 2

0 4 4 8

The following figure shows the possible ways the poles can fall for this sample input. The fractions in the figure indicate the probability of each state occurring.

Therefore, the probabilities that all poles have fallen by exactly the 1-st, 2-nd, 3-rd, 4-th earthquakes are 0, \frac{1}{4}, \frac{1}{4}, \frac{1}{2}, respectively. Multiply these by 16 to get 0, 4, 4, 8 for output.

Sample Input 3

8 1
5 0 6 3 8 1 7 2

Sample Output 3

0 64 32 48 24 28 28 32

The probabilities that all poles have fallen by exactly the 1-st, 2-nd, 3-rd, 4-th, 5-th, 6-th, 7-th, 8-th earthquakes are 0, \frac{1}{4}, \frac{1}{8}, \frac{3}{16}, \frac{3}{32}, \frac{7}{64}, \frac{7}{64}, \frac{1}{8}, respectively.

Sample Input 4

40 20
695 793 11 502 114 861 559 4 212 609 894 435 429 94 91 258 161 45 33 605 673 634 629 163 283 826 409 84 507 548 31 248 588 340 357 168 926 949 322 912

Sample Output 4

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 41942627 41942627 360709869

Not all poles will have fallen by the 37-th earthquake. The probabilities that all poles have fallen by exactly the 38, 39, 40-th earthquakes are \frac{3}{8}, \frac{3}{8}, \frac{1}{4}, respectively.
E - Wrong Scoreboard

実行時間制限: 9 sec / メモリ制限: 1024 MiB

配点 : 1000 点

問題文

AtCoder World Tour Finals 2800 には N 人の選手が参加し、全 5 問の問題が出題されました。 各問題には 1 点以上の整数の配点が付けられており、配点が広義単調増加になるように、問 1 から問 5 までの問題番号が付けられています。 ここで部分点はありません。 また、通常の AtCoder のルールと同様、以下の方法で順位付けが行われます。なお、本問では合計得点もペナルティも同じという状況は考えないことにします。

順位付けの方法合計得点の高い方が上の順位となる。同点の場合は、ペナルティが 1 秒でも少ない方が上の順位となる。


さて、AtCoder World Tour Finals の取材を担当している青木記者は、以下の情報をメモしました。

  1. 参加者数 N。
  2. 各選手がどの問題を解いたかの情報。A_{i,j}=1 のとき i 番目の選手 (1 \leq i \leq N) は問 j を正解し、A_{i,j}=0 のとき正解しなかった。
  3. 各選手の順位。i 番目の選手 (1 \leq i \leq N) は R_i 位を獲得した。

しかし、記事を書き始めようとしたとき、彼は配点およびペナルティの情報をメモしていないことに気付きました。 さらに、メモした情報に矛盾があるかもしれないことにも気付きました。 そこで以下の問題を解いてください。

メモ 1 およびメモ 2 が正しいと仮定する。 選手 i (1 \leq i \leq N) の実際の順位を D_i とするとき、二乗誤差の合計 (D_1 - R_1)^2 + (D_2 - R_2)^2 + \dots + (D_N - R_N)^2 として考えられる最小値を求めよ。

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

制約

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 3 \times 10^5
  • A_{i,1}, A_{i,2}, A_{i,3}, A_{i,4}, A_{i,5} は 0 または 1 (1 \leq i \leq N)
  • A_{i,1}, A_{i,2}, A_{i,3}, A_{i,4}, A_{i,5} の合計は 1 以上 (1 \leq i \leq N)
  • 1 \leq R_i \leq N (1 \leq i \leq N)
  • R_1, R_2, \dots, R_N は相異なる
  • すべてのテストケースにおける N の値の合計は 3 \times 10^5 以下
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。ここで \mathrm{case}_i は i 番目 (1 \leq i \leq T) のテストケースを意味します。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは、以下の形式で与えられます。

N
A_{1,1} A_{1,2} A_{1,3} A_{1,4} A_{1,5}
A_{2,1} A_{2,2} A_{2,3} A_{2,4} A_{2,5}
\vdots
A_{N,1} A_{N,2} A_{N,3} A_{N,4} A_{N,5}
R_1 R_2 \cdots R_N

出力

答えを出力してください。

入力例 1

6
4
0 1 1 0 0
1 0 0 1 0
1 1 0 1 0
1 0 1 0 0
1 2 3 4
8
0 1 0 0 0
1 1 0 1 0
0 1 1 0 1
1 0 0 0 0
1 1 0 1 0
0 1 0 0 0
0 0 0 1 0
0 1 1 1 1
7 4 2 8 3 6 5 1
6
1 1 0 0 0
0 0 1 0 0
1 1 1 0 0
0 0 0 1 0
1 1 1 1 0
0 0 0 0 1
1 2 3 4 5 6
6
1 1 0 0 0
0 0 1 0 0
1 1 1 0 0
0 0 0 1 0
1 1 1 1 0
0 0 0 0 1
6 5 4 3 2 1
20
0 0 0 0 1
0 0 1 0 0
1 1 0 0 1
1 0 1 0 1
0 0 0 1 1
0 0 1 1 1
1 1 1 1 0
1 1 0 1 0
0 0 1 1 0
1 0 1 0 0
0 1 0 0 1
0 1 1 1 1
1 1 1 1 1
0 1 0 1 0
1 0 0 0 1
1 1 1 0 0
0 1 1 1 0
0 0 0 1 0
1 1 1 0 1
1 1 0 1 1
7 18 3 5 19 11 13 2 4 10 14 15 17 6 16 9 8 12 1 20
15
0 0 1 1 0
0 0 0 1 0
0 0 0 0 1
0 0 1 1 1
1 1 0 0 1
0 1 1 1 0
1 1 1 1 1
0 1 1 0 1
1 1 0 1 0
1 0 0 1 1
1 0 1 0 0
1 1 0 1 1
0 1 0 1 0
1 1 0 0 0
0 1 0 0 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

出力例 1

6
0
26
0
1054
428

この入力には全部で 6 個のテストケースがありますが、まずは 1 つ目のテストケースについて説明します。

以下のような場合を考えます。

  • 1, 2, 3, 4, 5 問目の配点がそれぞれ 100 点、500 点、800 点、900 点、1300 点である。
  • 1, 2, 3, 4 番目の参加者のペナルティがそれぞれ 90 分、80 分、70 分、60 分である。

このとき、順位表は下表のようになり、二乗誤差の合計は (2-1)^2 + (3-2)^2 + (1-3)^2 + (4-4)^2 = 6 となります。二乗誤差の合計を 5 以下にする方法は存在しないため、6 が答えとなります。

参加者 問 1 問 2 問 3 問 4 問 5 合計点 ペナルティ 順位
1 番目 - 500 800 - - 1300 90 分 2 位
2 番目 100 - - 900 - 1000 80 分 3 位
3 番目 100 500 - 900 - 1500 70 分 1 位
4 番目 100 - 800 - - 900 60 分 4 位

続いて、2 つ目のテストケースについて説明します。

以下のような場合を考えます。

  • 1, 2, 3, 4, 5 問目の配点がそれぞれ 1000 点、1400 点、2000 点、2000 点、2718 点である。
  • 1, 2, \dots, 8 番目の参加者のペナルティがそれぞれ 295 分、286 分、242 分、236 分、277 分、288 分、187 分、299 分である。

このとき、順位表は下表のようになります。どの i (1 \leq i \leq N) についても i 番目の参加者の順位が R_i となっているため、二乗誤差の合計は 0 となります。

参加者 問 1 問 2 問 3 問 4 問 5 合計点 ペナルティ 順位
1 番目 - 1400 - - - 1400 295 分 7 位
2 番目 1000 1400 - 2000 - 4400 286 分 4 位
3 番目 - 1400 2000 - 2718 6118 242 分 2 位
4 番目 1000 - - - - 1000 236 分 8 位
5 番目 1000 1400 - 2000 - 4400 277 分 3 位
6 番目 - 1400 - - - 1400 288 分 6 位
7 番目 - - - 2000 - 2000 187 分 5 位
8 番目 - 1400 2000 2000 2718 8118 299 分 1 位


Score: 1000 points

Problem Statement

In the AtCoder World Tour Finals 2800, N contestants participated, and a total of five problems were presented. Each problem is assigned an integer score of at least 1 point, and the problems are numbered so that the scores are non-decreasing from problem 1 to problem 5. There are no partial points. Similar to the usual AtCoder rules, ranking is done as follows. In this problem, we do not consider the situation where multiple contestants have the same total score and penalty.

RankingThe contestant with the higher total score ranks higher. In case of a tie, the one with the smaller penalty ranks higher.

Now, Aoki, a reporter covering the finals, noted the following information:

  1. The number of participants N.
  2. Which problems each contestant solved. A_{i,j}=1 means the i-th contestant (1 \leq i \leq N) correctly solved problem j, and A_{i,j}=0 means they did not.
  3. The rank of each contestant. The i-th contestant (1 \leq i \leq N) was ranked R_i-th.

However, when he started writing the article, he realized he did not note the scores and penalties. Furthermore, he realized there might be inconsistencies in the information he noted. Now, solve the following problem.

Assume that he correctly noted information 1 and 2. Let D_i be the actual rank of contestant i (1 \leq i \leq N), and find the minimum possible total squared error (D_1 - R_1)^2 + (D_2 - R_2)^2 + \dots + (D_N - R_N)^2.

You have T test cases to process.

Constraints

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 3 \times 10^5
  • Each of A_{i,1}, A_{i,2}, A_{i,3}, A_{i,4}, A_{i,5} is 0 or 1 (1 \leq i \leq N).
  • The sum of A_{i,1}, A_{i,2}, A_{i,3}, A_{i,4}, A_{i,5} is at least 1 (1 \leq i \leq N).
  • 1 \leq R_i \leq N (1 \leq i \leq N)
  • R_1, R_2, \dots, R_N are distinct.
  • The total value of N across all test cases is at most 3 \times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format. Here \mathrm{case}_i represents the i-th test case (1 \leq i \leq T).

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
A_{1,1} A_{1,2} A_{1,3} A_{1,4} A_{1,5}
A_{2,1} A_{2,2} A_{2,3} A_{2,4} A_{2,5}
\vdots
A_{N,1} A_{N,2} A_{N,3} A_{N,4} A_{N,5}
R_1 R_2 \cdots R_N

Output

Print the answers.

Sample Input 1

6
4
0 1 1 0 0
1 0 0 1 0
1 1 0 1 0
1 0 1 0 0
1 2 3 4
8
0 1 0 0 0
1 1 0 1 0
0 1 1 0 1
1 0 0 0 0
1 1 0 1 0
0 1 0 0 0
0 0 0 1 0
0 1 1 1 1
7 4 2 8 3 6 5 1
6
1 1 0 0 0
0 0 1 0 0
1 1 1 0 0
0 0 0 1 0
1 1 1 1 0
0 0 0 0 1
1 2 3 4 5 6
6
1 1 0 0 0
0 0 1 0 0
1 1 1 0 0
0 0 0 1 0
1 1 1 1 0
0 0 0 0 1
6 5 4 3 2 1
20
0 0 0 0 1
0 0 1 0 0
1 1 0 0 1
1 0 1 0 1
0 0 0 1 1
0 0 1 1 1
1 1 1 1 0
1 1 0 1 0
0 0 1 1 0
1 0 1 0 0
0 1 0 0 1
0 1 1 1 1
1 1 1 1 1
0 1 0 1 0
1 0 0 0 1
1 1 1 0 0
0 1 1 1 0
0 0 0 1 0
1 1 1 0 1
1 1 0 1 1
7 18 3 5 19 11 13 2 4 10 14 15 17 6 16 9 8 12 1 20
15
0 0 1 1 0
0 0 0 1 0
0 0 0 0 1
0 0 1 1 1
1 1 0 0 1
0 1 1 1 0
1 1 1 1 1
0 1 1 0 1
1 1 0 1 0
1 0 0 1 1
1 0 1 0 0
1 1 0 1 1
0 1 0 1 0
1 1 0 0 0
0 1 0 0 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Sample Output 1

6
0
26
0
1054
428

This input contains six test cases. Let us explain the first one.

Consider the following scenario.

  • Problems 1, 2, 3, 4, 5 have 100, 500, 800, 900, 1300 points, respectively.
  • Contestants 1, 2, 3, 4 have penalties of 90, 80, 70, 60 minutes, respectively.

Then, the ranking will be as shown in the table below, where the total squared error is (2-1)^2 + (3-2)^2 + (1-3)^2 + (4-4)^2 = 6. There is no way to make the total squared error 5 or less, so the answer is 6.

Contestant Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Total score Penalty Rank
Contestant 1 - 500 800 - - 1300 90 minutes 2nd
Contestant 2 100 - - 900 - 1000 80 minutes 3rd
Contestant 3 100 500 - 900 - 1500 70 minutes 1st
Contestant 4 100 - 800 - - 900 60 minutes 4th

Now, let us explain the second test case.

Consider the following scenario.

  • Problems 1, 2, 3, 4, 5 have 1000, 1400, 2000, 2000, 2718 points, respectively.
  • Contestants 1, 2, \dots, 8 have penalties of 295, 286, 242, 236, 277, 288, 187, 299 minutes, respectively.

Then, the ranking will be as shown in the table below. For every i (1 \leq i \leq N), the rank of contestant i is R_i, so the total squared error is 0.

Contestant Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Total score Penalty Rank
Contestant 1 - 1400 - - - 1400 295 minutes 7th
Contestant 2 1000 1400 - 2000 - 4400 286 minutes 4th
Contestant 3 - 1400 2000 - 2718 6118 242 minutes 2nd
Contestant 4 1000 - - - - 1000 236 minutes 8th
Contestant 5 1000 1400 - 2000 - 4400 277 minutes 3rd
Contestant 6 - 1400 - - - 1400 288 minutes 6th
Contestant 7 - - - 2000 - 2000 187 minutes 5th
Contestant 8 - 1400 2000 2000 2718 8118 299 minutes 1st


F - Two Airlines

実行時間制限: 5 sec / メモリ制限: 2048 MiB

配点 : 1000 点

問題文

AtCoder 国は東西に並んでいる L+1 個の島から成り、これらは西から順に 0 から L までの番号が付けられています。 島々は航空路線で結ばれており、下図のように各 1 \leq i \leq L について、島 i-1 と島 i を双方向に結ぶ航空路線があります。 ここで、各航空路線は A 社または J 社が所有しており、島 i-1 と島 i を結ぶ路線は S_i 社が所有しています。

また、AtCoder 国には N 人の住民がおり、それぞれ 1 から N までの番号が付けられています。 住民 i は現在島 X_i にいます。

さらに、各住民はいずれか一方の航空会社の優待券を持っており、具体的には、住民 i は C_i 社の優待券を持っています。 優待券を持っている会社の航空路線は何度でも無料で乗ることができますが、そうでない会社の航空路線に乗るには、1 回当たり 1 コインを支払う必要があります。

今、島 0 に宝箱があります。これから AtCoder 国の住民で協力して、首都である島 L に宝箱を運びたいです。 最小で合計何コインで目的を達成できるかを求めてください。

なお、住民同士で宝箱の受け渡しをすることはできますが、優待券の受け渡しはできないものとします。

制約

  • 1 \leq L \leq 6 \times 10^4
  • 1 \leq N \leq 6 \times 10^4
  • S_i \ (1 \leq i \leq L) は A または J
  • 0 \leq X_i \leq L \ (1 \leq i \leq N)
  • C_i \ (1 \leq i \leq N) は A または J
  • L, N, X_i は整数

入力

入力は以下の形式で標準入力から与えられます。 

L N
S_1S_2\cdotsS_L
X_1 C_1
X_2 C_2
 \vdots
X_N C_N

入力の 2 行目は長さ L の文字列として与えられることに注意してください。

出力

答えを出力してください。

入力例 1

4 3
AAJJ
3 A
1 J
1 J

出力例 1

2

以下のような手順を選択すると、合計 2 コインで島 4 に宝箱を運ぶことができます。

  1. 住民 1 が島 3 から島 2 へ移動する。優待券の対象ではないので 1 コインを支払う。
  2. 住民 1 が島 2 から島 1 へ移動する。優待券の対象なのでコインを支払う必要はない。
  3. 住民 1 が島 1 から島 0 へ移動する。優待券の対象なのでコインを支払う必要はない。
  4. 住民 1 が宝箱を持つ。
  5. 住民 1 が宝箱を持った状態で、島 0 から島 1 へ移動する。優待券の対象なのでコインを支払う必要はない。
  6. 住民 1 が住民 2 に宝箱を渡す。
  7. 住民 2 が宝箱を持った状態で、島 1 から島 2 へ移動する。優待券の対象ではないので 1 コインを支払う。
  8. 住民 2 が宝箱を持った状態で、島 2 から島 3 へ移動する。優待券の対象なのでコインを支払う必要はない。
  9. 住民 2 が宝箱を持った状態で、島 3 から島 4 へ移動する。優待券の対象なのでコインを支払う必要はない。

入力例 2

8 3
JJAAJJAJ
2 A
6 A
8 J

出力例 2

6

入力例 3

8 6
JJAAJJAJ
2 A
6 A
8 J
8 J
8 J
8 J

出力例 3

4

Score: 1000 points

Problem Statement

The Republic of AtCoder consists of L+1 islands aligned east-west, numbered 0 to L from west to east. The islands are connected by air routes, where for each 1 \leq i \leq L, there is a bidirectional air route between islands i-1 and i, as shown in the figure below. Each air route is owned by company A or company J, and the route between islands i-1 and i is owned by company S_i.

The nation has N residents, numbered 1 to N. Resident i is currently on island X_i.

Each resident has a coupon of one of the companies. Specifically, resident i has a coupon of company C_i. With a coupon, a resident can take that company's routes for free any number of times, but taking a route of the other company costs 1 coin per trip.

Now, there is a treasure chest on island 0. The residents want to cooperate to carry it to the capital, which is on island L. Determine the minimum total number of coins required to achieve this goal.

The residents can pass the treasure chest to each other, but not their coupons.

Constraints

  • 1 \leq L \leq 6 \times 10^4
  • 1 \leq N \leq 6 \times 10^4
  • S_i \ (1 \leq i \leq L) is A or J.
  • 0 \leq X_i \leq L \ (1 \leq i \leq N)
  • C_i \ (1 \leq i \leq N) is A or J.
  • L, N, and X_i are integers.

Input

The input is given from Standard Input in the following format:

L N
S_1S_2\cdotsS_L
X_1 C_1
X_2 C_2
 \vdots
X_N C_N

Note that the second line is given as a string of length L.

Output

Print the answer.

Sample Input 1

4 3
AAJJ
3 A
1 J
1 J

Sample Output 1

2

The following procedure carries the treasure chest to island 4 for a total of 2 coins.

  1. Resident 1 moves from island 3 to island 2. The route is not covered by the coupon, so 1 coin is paid.
  2. Resident 1 moves from island 2 to island 1. The route is covered by the coupon, so no coin is needed.
  3. Resident 1 moves from island 1 to island 0. The route is covered by the coupon, so no coin is needed.
  4. Resident 1 picks up the treasure chest.
  5. Resident 1, carrying the treasure chest, moves from island 0 to island 1. The route is covered by the coupon, so no coin is needed.
  6. Resident 1 passes the treasure chest to resident 2.
  7. Resident 2, carrying the treasure chest, moves from island 1 to island 2. The route is not covered by the coupon, so 1 coin is paid.
  8. Resident 2, carrying the treasure chest, moves from island 2 to island 3. The route is covered by the coupon, so no coin is needed.
  9. Resident 2, carrying the treasure chest, moves from island 3 to island 4. The route is covered by the coupon, so no coin is needed.

Sample Input 2

8 3
JJAAJJAJ
2 A
6 A
8 J

Sample Output 2

6

Sample Input 3

8 6
JJAAJJAJ
2 A
6 A
8 J
8 J
8 J
8 J

Sample Output 3

4