Ｓｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 289）

A - flip

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

配点 : 100 点

問題文

0 と 1 の 2 種類の文字からなる文字列 s が与えられます。 s に含まれる 0 を 1 に、1 を 0 に置き換えた文字列を出力してください。

制約

s の長さは 1 以上 10 以下
s は 0 と 1 の 2 種類の文字からなる

入力

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

出力

答えを 1 行で出力せよ。

入力例 1

出力例 1

s の 1 文字目は 1 なので、1 文字目に出力すべき文字は 0 です。 s の 2 文字目は 0 なので、2 文字目に出力すべき文字は 1 です。

入力例 2

出力例 2

入力例 3

100100001

出力例 3

011011110

Score : 100 points

Problem Statement

You are given a string s consisting of two kinds of characters, 0 and 1. Print the string obtained by replacing 0 with 1 and 1 with 0 in s.

Constraints

The length of s is between 1 and 10, inclusive.
s consists of two kinds of characters, 0 and 1.

Input

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

Output

Print the answer in a single line.

Sample Input 1

Sample Output 1

The 1-st character of s is 1, so the 1-st character to print is 0. The 2-nd character of s is 0, so the 2-nd character to print is 1.

Sample Input 2

Sample Output 2

Sample Input 3

100100001

Sample Output 3

011011110

B - レ

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

配点 : 200 点

問題文

高橋君は漢文の勉強をしていて、漢字を読む順番が分からず困っています。高橋君を助けましょう！

1 から N までの N 個の整数が小さい方から順に 1 列に並んでいます。
整数の間に M 個の「レ」が挟まっています。i 個目の「レ」は、整数 a_i と整数 a_i + 1 の間にあります。

あなたは次の手順に従って、N 個の整数を 1 回ずつ全て読みます。

まず、頂点に 1 から N までの番号がついた N 頂点 M 辺の無向グラフ G を考える。i 本目の辺は頂点 a_i と頂点 a_i + 1 を結んでいる。
そして、読まれていない整数が無くなるまで次の操作を繰り返す。
- 読まれていない整数のうち最小のものを x とする。頂点 x が含まれる連結成分 C を選び、C に含まれる頂点の番号を大きい方から順に全て読む。

例えば、整数と「レ」が

という順番で並んでいる場合を考えます。(この場合 N = 5, M = 3, a = (1, 3, 4) です。)
このとき、整数が読まれる順番は以下の手順によって 2, 1, 5, 4, 3 に決定します。

最初、読まれていない整数のうち最小のものは 1 であり、グラフ G の頂点 1 を含む連結成分に含まれる頂点は \lbrace 1, 2 \rbrace である。よって 2, 1 がこの順で読まれる。
次に、読まれていない整数のうち最小のものは 3 であり、グラフ G の頂点 3 を含む連結成分に含まれる頂点は \lbrace 3, 4, 5 \rbrace である。よって 5, 4, 3 がこの順で読まれる。
すべての整数が読まれたので手順を終了する。

N, M, (a_1, a_2, \dots, a_M) が入力として与えられるので、 N 個の整数を読む順番を出力してください。

連結成分とは

あるグラフの 部分グラフ とは、元のグラフのいくつかの頂点といくつかの辺を選んでできるグラフのことをいいます。
グラフが連結であるとは、グラフに含まれるすべての頂点同士が辺を経由して互いに行き来できることをいいます。
連結成分 とは、連結な部分グラフのうち、そのグラフを含んだより大きい連結な部分グラフが存在しないものをいいます。

制約

1 \leq N \leq 100
0 \leq M \leq N - 1
1 \leq a_1 \lt a_2 \lt \dots \lt a_M \leq N-1
入力される値は全て整数

入力

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

N M
a_1 a_2 \dots a_M

出力

答えを以下の形式で出力せよ。ここで p_i は、i 番目に読まれる整数を意味する。

p_1 p_2 \dots p_N

入力例 1

5 3
1 3 4

出力例 1

2 1 5 4 3

問題文の例にある通り、整数と「レ」が

という順で並んでいる場合は 2, 1, 5, 4, 3 の順で読みます。

入力例 2

5 0

出力例 2

1 2 3 4 5

「レ」が存在しない場合もあります。

入力例 3

10 6
1 2 3 7 8 9

出力例 3

4 3 2 1 5 6 10 9 8 7

Score : 200 points

Problem Statement

Studying Kanbun, Takahashi is having trouble figuring out the order to read words. Help him out!

There are N integers from 1 through N arranged in a line in ascending order.
Between them are M "レ" marks. The i-th "レ" mark is between the integer a_i and integer (a_i + 1).

You read each of the N integers once by the following procedure.

Consider an undirected graph G with N vertices numbered 1 through N and M edges. The i-th edge connects vertex a_i and vertex (a_i+1).
Repeat the following operation until there is no unread integer:
- let x be the minimum unread integer. Choose the connected component C containing vertex x, and read all the numbers of the vertices contained in C in descending order.

For example, suppose that integers and "レ" marks are arranged in the following order:

(In this case, N = 5, M = 3, and a = (1, 3, 4).)
Then, the order to read the integers is determined to be 2, 1, 5, 4, and 3, as follows:

At first, the minimum unread integer is 1, and the connected component of G containing vertex 1 has vertices \lbrace 1, 2 \rbrace, so 2 and 1 are read in this order.
Then, the minimum unread integer is 3, and the connected component of G containing vertex 3 has vertices \lbrace 3, 4, 5 \rbrace, so 5, 4, and 3 are read in this order.
Now that all integers are read, terminate the procedure.

Given N, M, and (a_1, a_2, \dots, a_M), print the order to read the N integers.

What is a connected component?

A subgraph of a graph is a graph obtained by choosing some vertices and edges from the original graph.
A graph is said to be connected if and only if one can travel between any two vertices in the graph via edges.
A connected component is a connected subgraph that is not contained in any larger connected subgraph.

Constraints

1 \leq N \leq 100
0 \leq M \leq N - 1
1 \leq a_1 \lt a_2 \lt \dots \lt a_M \leq N-1
All values in the input are integers.

Input

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

N M
a_1 a_2 \dots a_M

Output

Print the answer in the following format, where p_i is the i-th integers to read.

p_1 p_2 \dots p_N

Sample Input 1

5 3
1 3 4

Sample Output 1

2 1 5 4 3

As described in the Problem Statement, if integers and "レ" marks are arranged in the following order:

then the integers are read in the following order: 2, 1, 5, 4, and 3.

Sample Input 2

5 0

Sample Output 2

1 2 3 4 5

There may be no "レ" mark.

Sample Input 3

10 6
1 2 3 7 8 9

Sample Output 3

4 3 2 1 5 6 10 9 8 7

C - Coverage

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

配点 : 300 点

問題文

1 以上 N 以下の整数からなる集合が M 個あり、順に S_1, S_2, \dots, S_M と呼びます。
S_i は C_i 個の整数 a_{i, 1}, a_{i, 2}, \dots, a_{i, C_i} からなります。

M 個の集合から 1 個以上の集合を選ぶ方法は 2^M-1 通りあります。
このうち、次の条件を満たす選び方は何通りありますか？

1 \leq x \leq N を満たす全ての整数 x に対して、選んだ集合の中に x を含む集合が少なくとも 1 個存在する。

制約

1 \leq N \leq 10
1 \leq M \leq 10
1 \leq C_i \leq N
1 \leq a_{i,1} \lt a_{i,2} \lt \dots \lt a_{i,C_i} \leq N
入力される値は全て整数

入力

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

N M
C_1
a_{1,1} a_{1,2} \dots a_{1,C_1}
C_2
a_{2,1} a_{2,2} \dots a_{2,C_2}
\vdots
C_M
a_{M,1} a_{M,2} \dots a_{M,C_M}

出力

問題文の条件を満たす集合の選び方の数を出力せよ。

入力例 1

出力例 1

入力で与えられている集合はそれぞれ S_1 = \lbrace 1, 2 \rbrace, S_2 = \lbrace 1, 3 \rbrace, S_3 = \lbrace 2 \rbrace です。
問題文の条件を満たす集合の選び方は次の 3 通りです。

S_1, S_2 を選ぶ。
S_1, S_2, S_3 を選ぶ。
S_2, S_3 を選ぶ。

入力例 2

出力例 2

問題文の条件を満たす選び方が存在しない場合もあります。

入力例 3

出力例 3

Score : 300 points

Problem Statement

There are M sets, called S_1, S_2, \dots, S_M, consisting of integers between 1 and N.
S_i consists of C_i integers a_{i, 1}, a_{i, 2}, \dots, a_{i, C_i}.

There are (2^M-1) ways to choose one or more sets from the M sets.
How many of them satisfy the following condition?

For all integers x such that 1 \leq x \leq N, there is at least one chosen set containing x.

Constraints

1 \leq N \leq 10
1 \leq M \leq 10
1 \leq C_i \leq N
1 \leq a_{i,1} \lt a_{i,2} \lt \dots \lt a_{i,C_i} \leq N
All values in the input are integers.

Input

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

N M
C_1
a_{1,1} a_{1,2} \dots a_{1,C_1}
C_2
a_{2,1} a_{2,2} \dots a_{2,C_2}
\vdots
C_M
a_{M,1} a_{M,2} \dots a_{M,C_M}

Output

Print the number of ways to choose sets that satisfy the conditions in the Problem Statement.

Sample Input 1

Sample Output 1

The sets given in the input are S_1 = \lbrace 1, 2 \rbrace, S_2 = \lbrace 1, 3 \rbrace, S_3 = \lbrace 2 \rbrace.
The following three ways satisfy the conditions in the Problem Statement:

choosing S_1, S_2;
choosing S_1, S_2, S_3;
choosing S_2, S_3.

Sample Input 2

Sample Output 2

There may be no way to choose sets that satisfies the conditions in the Problem Statement.

Sample Input 3

Sample Output 3

D - Step Up Robot

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

配点 : 400 点

問題文

無限に続く階段があります。一番下は 0 段目で、1 段のぼるごとに 1 段目、2 段目と続きます。

0 段目に階段登りロボットがいます。階段登りロボットは、一回の動作で A _ 1,A _ 2,\ldots,A _ N 段ぶん階段をのぼることができます。つまり、階段登りロボットが i 段目にいるとき、一回動作をした後は i+A _ 1 段目、i+A _ 2 段目、⋯、i+A _ N 段目のいずれかにいることができます。それ以外の段数を一回の動作でのぼることはできません。階段登りロボットは階段を下ることもできません。

階段の B _ 1,B _ 2,\ldots,B _ M 段目にはモチが設置されています。モチが設置されている段へのぼるとロボットは動けなくなり、他の段に移動することができなくなります。

階段登りロボットは階段のちょうど X 段目にのぼりたいです。階段登りロボットが階段のちょうど X 段目にのぼることが可能か判定してください。

制約

1\leq N\leq10
1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^5
1\leq M\leq10^5
1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\lt X\leq10^5
入力はすべて整数

入力

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

N
A _ 1 A _ 2 \ldots A _ N
M
B _ 1 B _ 2 \ldots B _ M
X

出力

階段登りロボットが階段のちょうど X 段目にのぼることができるとき Yes を、そうでないとき No を 1 行に出力せよ。

入力例 1

出力例 1

Yes

例えば、次のようにして 15 段目に到達することができます。

階段を 3 段のぼる。ロボットは 3 段目に移動する。
階段を 4 段のぼる。ロボットは 7 段目に移動する。
階段を 5 段のぼる。ロボットは 12 段目に移動する。
階段を 3 段のぼる。ロボットは 15 段目に移動する。

入力例 2

出力例 2

No

どのように移動しても階段登りロボットが階段のちょうど 8 段目にいることはできません。

入力例 3

4
2 5 7 8
5
2 9 10 11 19
20

出力例 3

Yes

Score : 400 points

Problem Statement

There is a staircase with infinite steps. The foot of the stairs is the 0-th step, the next step is the 1-st step, the next is the 2-nd, and so on.

There is a stair-climbing robot on the 0-th step. The robot can climb up A _ 1,A _ 2,\ldots, or A _ N steps at a time. In other words, when the robot is on the i-th step, it can step onto one of the (i+A _ 1)-th step, (i+A _ 2)-th step, \ldots, and (i+A _ N)-th step, but not onto the others in a single step. The robot cannot descend the stairs, either.

There are traps on the B _ 1-th, B _ 2-th, \ldots, and B _ M-th steps. Once the robot steps onto a step with a trap, it cannot move anymore.

The robot wants to step onto the X-th step. Determine whether it is possible to do so.

Constraints

1\leq N\leq10
1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^5
1\leq M\leq10^5
1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\lt X\leq10^5
All values in the input are integers.

Input

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

N
A _ 1 A _ 2 \ldots A _ N
M
B _ 1 B _ 2 \ldots B _ M
X

Output

In a single line, print Yes if the robot can step onto the X-th step, and No otherwise.

Sample Input 1

Sample Output 1

Yes

For example, the robot can reach the 15-th step as follows.

Climb up 3 steps. The robot is now on the 3-rd step.
Climb up 4 steps. The robot is now on the 7-th step.
Climb up 5 steps. The robot is now on the 12-th step.
Climb up 3 steps. The robot is now on the 15-th step.

Sample Input 2

Sample Output 2

No

No matter how the robot moves, it cannot step onto the 8-th step.

Sample Input 3

4
2 5 7 8
5
2 9 10 11 19
20

Sample Output 3

Yes

E - Swap Places

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

配点 : 500 点

問題文

頂点に 1 から N までの、辺に 1 から M までの番号がついた N 頂点 M 辺の単純無向グラフがあります。辺 i は頂点 u_i と頂点 v_i を結んでいます。
また、全ての頂点は赤か青のいずれか一方で塗られています。頂点 i の色は C_i で表されて、C_i が 0 ならば頂点 i は赤く、1 ならば頂点 i は青く塗られています。

今、高橋君が頂点 1 に、青木君が頂点 N にいます。
2 人は次の行動を 0 回以上好きな回数繰り返します。

2 人が同時に、今いる頂点に隣接している頂点のいずれか 1 個に移動する。
ただし、高橋君の移動先の頂点の色と、青木君の移動先の頂点の色は異なる必要がある。

上記の行動を繰り返すことで、高橋君が頂点 N に、青木君が頂点 1 にいる状態にできますか？
可能である場合は必要な行動回数の最小値を答えてください。不可能である場合は -1 を出力してください。

入力のはじめに T が与えられるので、T 個のテストケースについて問題を解いてください。

制約

1 \leq T \leq 1000
2 \leq N \leq 2000
1 \leq M \leq \min(\frac{N(N-1)}{2}, 2000)
C_i \in \lbrace 0, 1 \rbrace
1 \leq u_i, v_i \leq N
入力で与えられるグラフは単純
入力される値は全て整数
全てのテストケースに対する N の総和は 2000 を超えない。
全てのテストケースに対する M の総和は 2000 を超えない。

入力

入力は以下の形式で標準入力から与えられる。ここで \text{test}_i は i 番目のテストケースを意味する。

T
\text{test}_1
\text{test}_2
\vdots
\text{test}_T

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

N M
C_1 C_2 \dots C_N
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

T 行出力せよ。i 行目には i 番目のテストケースに対する答えを出力せよ。
各テストケースでは、高橋君が頂点 N に、青木君が頂点 1 にいる状態にできる場合は必要な行動回数の最小値を、できない場合は -1 を出力せよ。

入力例 1

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

出力例 1

3
-1
3

1 番目のテストケースでは、高橋君と青木君は以下のように行動することで、 3 回の行動で目的の状態を達成することができて、これが最小です。

高橋君が頂点 3 に、青木君が頂点 2 に移動する。
高橋君が頂点 2 に、青木君が頂点 3 に移動する。
高橋君が頂点 4 に、青木君が頂点 1 に移動する。

ここで、1 回目の移動で高橋君と青木君がともに頂点 2 に移動することはできないのに注意してください。(なぜならば、高橋君の移動先の頂点の色と青木君の移動先の頂点の色は異なる必要があるからです。)

2 番目のテストケースでは、2 人はどのように行動しても目的の状態を達成することはできません。

Score : 500 points

Problem Statement

There is a simple undirected graph with N vertices numbered 1 through N and M edges numbered 1 through M. Edge i connects vertex u_i and vertex v_i.
Every vertex is painted either red or blue. The color of vertex i is represented by C_i; vertex i is painted red if C_i is 0 and blue if C_i is 1.

Now, Takahashi is on vertex 1 and Aoki is on vertex N.
They may repeat the following move zero or more times.

Each of the two simultaneously moves to a vertex adjacent to the current vertex.
Here, the vertices that Takahashi and Aoki move to must have different colors.

By repeating the move above, can Takahashi and Aoki simultaneously end up on vertices N and 1, respectively?
If it is possible, find the minimum number of moves required. If it is impossible, print -1.

You are given T at the beginning of the input. Solve the problem for T test cases.

Constraints

1 \leq T \leq 1000
2 \leq N \leq 2000
1 \leq M \leq \min(\frac{N(N-1)}{2}, 2000)
C_i \in \lbrace 0, 1 \rbrace
1 \leq u_i, v_i \leq N
The graph given in the input is simple.
All values in the input are integers.
The sum of N over all test cases does not exceed 2000.
The sum of M over all test cases does not exceed 2000.

Input

The input is given from Standard Input in the following format, where \text{test}_i denotes the i-th test case:

T
\text{test}_1
\text{test}_2
\vdots
\text{test}_T

Each test case is given in the following format:

N M
C_1 C_2 \dots C_N
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print T lines. The i-th line should contain the answer to the i-th test case.
For each test case, print the minimum number of moves required for Takahashi and Aoki to simultaneously end up in vertices N and 1, respectively, if it is possible, and -1 otherwise.

Sample Input 1

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

Sample Output 1

3
-1
3

For the 1-st test case, Takahashi and Aoki can achieve the objective by making the following 3 moves, which is the minimum number:

Takahashi moves to vertex 3, and Aoki moves to vertex 2.
Takahashi moves to vertex 2, and Aoki moves to vertex 3.
Takahashi moves to vertex 4, and Aoki moves to vertex 1.

Note that in the 1-st move, it is disallowed that both Takahashi and Aoki move to vertex 2 (because the colors of vertices that Takahashi and Aoki move to must be different.)

For the 2-nd case, no matter how they move, they cannot achieve the objective.

F - Teleporter Takahashi

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

配点 : 500 点

問題文

xy 平面上に高橋くんがいます。はじめ、高橋くんは点 (s _ x,s _ y) にいます。高橋くんは、点 (t _ x,t _ y) に移動したいです。

xy 平面上に、長方形 R\coloneqq\lbrace(x,y)\mid a-0.5\leq x\leq b+0.5,c-0.5\leq y\leq d+0.5\rbrace があります。次の操作を考えます。

長方形 R に含まれる格子点 (x,y) をひとつ選ぶ。点 (x,y) を中心に高橋くんはいまいる位置と対称な位置に瞬間移動する。

上の操作を 0 回以上 10^6 回以下繰り返して、高橋くんが点 (t _ x,t _ y) にいるようにできるか判定してください。できる場合、高橋くんが点 (t _ x,t _ y) に移動することができるような操作の列を 1 つ構成してください。

制約

0\leq s _ x,s _ y,t _ x,t _ y\leq2\times10^5
0\leq a\leq b\leq2\times10^5
0\leq c\leq d\leq2\times10^5
入力はすべて整数

入力

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

s _ x s _ y
t _ x t _ y
a b c d

出力

1 行目には、操作を 0 回以上 10^6 回以下繰り返して高橋くんが点 (t _ x,t _ y) に到達できるなら Yes 、そうでなければ No と出力せよ。 1 行目で Yes と出力したとき、かつそのときに限り、あなたが構成した操作列の長さを d としてさらに d 行出力せよ（d は 0\leq d\leq10^6 を満たさなければならない）。 1+i 行目 (1\leq i\leq d) には、i 回目の操作で選んだ点 (x, y)\in R の座標をこの順に空白区切りで出力せよ。

入力例 1

1 2
7 8
7 9 0 3

出力例 1

例えば、次のようにして (1,2) から (7,8) へ移動することができます。

点 (7,0) を選ぶ。高橋くんは (13,-2) に移動する。
点 (9,3) を選ぶ。高橋くんは (5,8) に移動する。
点 (7,1) を選ぶ。高橋くんは (9,-6) に移動する。
点 (8,1) を選ぶ。高橋くんは (7,8) に移動する。

条件を満たす操作の列であれば何を出力しても正答となるので、例えば

と出力しても正答となります。

入力例 2

0 0
8 4
5 5 0 0

出力例 2

No

どのように操作しても点 (8,4) に移動することはできません。

入力例 3

1 4
1 4
100 200 300 400

出力例 3

Yes

高橋くんがはじめから目的地にいる場合もあります。

入力例 4

22 2
16 7
14 30 11 14

出力例 4

No

Score : 500 points

Problem Statement

Takahashi is on an xy-plane. Initially, he is at point (s _ x,s _ y), and he wants to reach point (t _ x,t _ y).

On the xy-plane is a rectangle R\coloneqq\lbrace(x,y)\mid a-0.5\leq x\leq b+0.5,c-0.5\leq y\leq d+0.5\rbrace. Consider the following operation:

Choose a lattice point (x,y) contained in the rectangle R. Takahashi teleports to the point symmetric to his current position with respect to point (x,y).

Determine if he can reach point (t _ x,t _ y) after repeating the operation above between 0 and 10^6 times, inclusive. If it is possible, construct a sequence of operations that leads him to point (t _ x,t _ y).

Constraints

0\leq s _ x,s _ y,t _ x,t _ y\leq2\times10^5
0\leq a\leq b\leq2\times10^5
0\leq c\leq d\leq2\times10^5
All values in the input are integers.

Input

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

s _ x s _ y
t _ x t _ y
a b c d

Output

In the first line, print Yes if Takahashi can reach point (t _ x,t _ y) after repeating the operation between 0 and 10^6 times, inclusive, and No otherwise. If and only if you print Yes in the first line, print d more lines, where d is the length of the sequence of operations you have constructed (d must satisfy 0\leq d\leq10^6). The (1+i)-th line (1\leq i\leq d) should contain the space-separated coordinates of the point (x, y)\in R, in this order, that is chosen in the i-th operation.

Sample Input 1

1 2
7 8
7 9 0 3

Sample Output 1

For example, the following choices lead him from (1,2) to (7,8).

Choose (7,0). Takahashi moves to (13,-2).
Choose (9,3). Takahashi moves to (5,8).
Choose (7,1). Takahashi moves to (9,-6).
Choose (8,1). Takahashi moves to (7,8).

Any output that satisfies the conditions is accepted; for example, printing

is also accepted.

Sample Input 2

0 0
8 4
5 5 0 0

Sample Output 2

No

No sequence of operations leads him to point (8,4).

Sample Input 3

1 4
1 4
100 200 300 400

Sample Output 3

Yes

Takahashi may already be at the destination in the beginning.

Sample Input 4

22 2
16 7
14 30 11 14

Sample Output 4

No

G - Shopping in AtCoder store

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

配点 : 600 点

問題文

高橋くんは AtCoder 商店を経営しています。 AtCoder 商店には N 人の客が訪れ、M 個の商品が売られています。 i 番目 (1\leq i\leq N) の客は購買意欲 B _ i を持っています。 j 番目 (1\leq j\leq M) の商品の商品価値は C _ j です。

高橋くんはそれぞれの商品に値段をつけます。 i 番目の客は、j 番目の商品の値段 P _ j が次の条件を満たすような商品のみを、すべて 1 個ずつ購入します。

B _ i+C _ j\geq P _ j

j=1,2,\ldots,M について、高橋くんが売り上げが最大になるような値段をつけたときの j 番目の商品の売り上げを求めてください。ただし、j 番目の商品の売り上げとは、P _ j に j 番目の商品を買う人数をかけたものです。

制約

1\leq N\leq2\times10^5
1\leq M\leq2\times10^5
0\leq B _ i\leq10^9\quad(1\leq i\leq N)
0\leq C _ i\leq10^9\quad(1\leq i\leq M)
入力はすべて整数

入力

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

N M
B _ 1 B _ 2 \ldots B _ N
C _ 1 C _ 2 \ldots C _ M

出力

j=1,2,\ldots,M について、j 番目の商品の売り上げを空白区切りで 1 行に出力せよ。

入力例 1

5 4
100 200 300 400 500
120 370 470 80

出力例 1

1280 2350 2850 1140

たとえば、1 番目の商品の値段を 320 にすると、2,3,4,5 番目の客が購入します。 1 番目の商品の売り上げは 1280 になります。 1 番目の商品の売り上げを 1280 より大きくすることはできないので、1 番目に出力すべき値は 1280 です。

入力例 2

4 4
0 2 10 2
13 13 0 4

出力例 2

52 52 10 18

購買意欲が同じ 2 人や、商品価値が同じ 2 品があることもあります。

入力例 3

12 15
16 592 222 983 729 338 747 61 451 815 838 281
406 319 305 519 317 590 507 946 365 5 673 478 340 176 2

出力例 3

6280 5466 5382 7410 5454 8120 7290 11680 5870 3670 8950 7000 5620 4608 3655

入力例 4

5 5
1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000

出力例 4

10000000000 10000000000 10000000000 10000000000 10000000000

売り上げが 32\operatorname{bit} 整数におさまらない場合があることに注意してください。

Score : 600 points

Problem Statement

Takahashi runs AtCoder store. N customers visit the store, and M items are sold in the store. The motivation of the i-th (1\leq i\leq N) customer is B _ i. The value of the j-th (1\leq j\leq M) item is C _ j.

Takahashi sets a price for each item. The i-th customer buys one j-th item if and only if its price P _ j satisfies:

B _ i+C _ j\geq P _ j.

For each j=1,2,\ldots,M, find the gross sale of the j-th item when Takahashi sets the price so that the sale is maximized. The gross sale of the j-th item is defined as the product of P _ j and the number of customers that buys the j-th item.

Constraints

1\leq N\leq2\times10^5
1\leq M\leq2\times10^5
0\leq B _ i\leq10^9\quad(1\leq i\leq N)
0\leq C _ i\leq10^9\quad(1\leq i\leq M)
All values in the input are integers.

Input

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

N M
B _ 1 B _ 2 \ldots B _ N
C _ 1 C _ 2 \ldots C _ M

Output

Print a line containing the gross sale of the j-th item for each j=1,2,\ldots,M, separated by spaces.

Sample Input 1

5 4
100 200 300 400 500
120 370 470 80

Sample Output 1

1280 2350 2850 1140

For example, he may set the price of the 1-st item to 320; then the 2-nd, 3-rd, 4-th, and 5-th customers will buy one. The gross sale of the 1-st item will be 1280. Since he cannot make the gross sale of the 1-st item greater than 1280, the 1-st value to be printed is 1280.

Sample Input 2

4 4
0 2 10 2
13 13 0 4

Sample Output 2

52 52 10 18

Two customers may have the same motivation. Also, two items may have the same value.

Sample Input 3

12 15
16 592 222 983 729 338 747 61 451 815 838 281
406 319 305 519 317 590 507 946 365 5 673 478 340 176 2

Sample Output 3

6280 5466 5382 7410 5454 8120 7290 11680 5870 3670 8950 7000 5620 4608 3655

Sample Input 4

5 5
1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 4

10000000000 10000000000 10000000000 10000000000 10000000000

Note that the gross sales may not fit into a 32-bit integer type.

Ex - Trio

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

配点 : 600 点

問題文

数直線上に人 1, 人 2, 人 3 がいます。時刻 0 の時点で、人 1 は地点 A に、人 2 は地点 B に、人 3 は地点 C にいます。
ここで A, B, C はすべて整数で、A \equiv B \equiv C \pmod{2} が成り立ちます。

3 人は時刻 0 からランダムウォークを行います。詳しく説明すると、時刻 t ( t は非負整数 ) の時点で地点 x にいる人は、時刻 t+1 に地点 x-1 と地点 x+1 のいずれか一方に等確率で移動します。(すべての移動する方向の選択は、ランダムかつ独立です。)

このとき、時刻 0 以降で、時刻 T に初めて 3 人が同じ地点にいる状態になる確率を \text{mod } 998244353 で計算してください。

有理数 \text{mod }998244353 とは

求める確率は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。

制約

0 \leq A, B, C, T \leq 10^5
A \equiv B \equiv C \pmod{2}
A, B, C, T は整数

入力

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

A B C T

出力

時刻 T に初めて 3 人が同じ地点にいる状態になる確率を \text{mod } 998244353 で計算して、答えを出力せよ。

入力例 1

1 1 3 1

出力例 1

873463809

時刻 1 に初めて 3 人が同じ地点にいる状態になる確率は \frac{1}{8} です。873463809 \times 8 \equiv 1 \pmod{998244353} なので 873463809 を出力します。

入力例 2

0 0 0 0

出力例 2

時刻 0 の時点ですでに 3 人が同じ地点にいる場合もあります。

入力例 3

0 2 8 9

出力例 3

744570476

入力例 4

47717 21993 74147 76720

出力例 4

844927176

Score : 600 points

Problem Statement

On a number line are person 1, person 2, and person 3. At time 0, person 1 is at point A, person 2 is at point B, and person 3 is at point C.
Here, A, B, and C are all integers, and A \equiv B \equiv C \pmod{2}.

At time 0, the three people start random walks. Specifically, a person that is at point x at time t (t is a non-negative integer) moves to point (x-1) or point (x+1) at time (t+1) with equal probability. (All choices of moves are random and independent.)

Find the probability, modulo 998244353, that it is at time T that the three people are at the same point for the first time.

What is rational number modulo 998244353?

We can prove that the sought probability is always a rational number. Moreover, under the Constraints of this problem, when the value is represented as \frac{P}{Q} by two coprime integers P and Q, we can prove that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find such R.

Constraints

0 \leq A, B, C, T \leq 10^5
A \equiv B \equiv C \pmod{2}
A, B, C, and T are integers.

Input

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

A B C T

Output

Find the probability, modulo 998244353, that it is at time T that the three people are at the same point for the first time, and print the answer.

Sample Input 1

1 1 3 1

Sample Output 1

873463809

The three people are at the same point for the first time at time 1 with the probability \frac{1}{8}. Since 873463809 \times 8 \equiv 1 \pmod{998244353}, 873463809 should be printed.

Sample Input 2

0 0 0 0

Sample Output 2

The three people may already be at the same point at time 0.

Sample Input 3

0 2 8 9

Sample Output 3

744570476

Sample Input 4

47717 21993 74147 76720

Sample Output 4

844927176