A - New Generation ABC

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

AtCoder Beginner Contest は、今回で 214 回目の開催となりました。

今までの AtCoder Beginner Contest において、出題される問題数は次のように変化しました。

  • 1 回目から 125 回目までは 4 問
  • 126 回目から 211 回目までは 6 問
  • 212 回目から 214 回目までは 8 問

N 回目の AtCoder Beginner Contest において出題された問題数を求めてください。

制約

  • 1 \leq N \leq 214
  • 入力は全て整数である。

入力

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

N

出力

答えを出力せよ。


入力例 1

214

出力例 1

8

入力例 2

1

出力例 2

4

入力例 3

126

出力例 3

6

Score : 100 points

Problem Statement

This is the 214-th AtCoder Beginner Contest (ABC).

The ABCs so far have had the following number of problems.

  • The 1-st through 125-th ABCs had 4 problems each.
  • The 126-th through 211-th ABCs had 6 problems each.
  • The 212-th through 214-th ABCs have 8 problems each.

Find the number of problems in the N-th ABC.

Constraints

  • 1 \leq N \leq 214
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.


Sample Input 1

214

Sample Output 1

8

Sample Input 2

1

Sample Output 2

4

Sample Input 3

126

Sample Output 3

6
B - Seats

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 個の座席が並んでおり、座席には 1, 2, \ldots, N の番号が付けられています。

座席の状態は #, . からなる長さ N の文字列 S によって与えられます。S の i 文字目が # のとき座席 i には人が座っていることを表し、S の i 文字目が . のとき座席 i には人が座っていないことを表します。

1 以上 N - 2 以下の整数 i であって、以下の条件を満たすものの個数を求めてください。

  • 座席 i, i + 2 には人が座っており、座席 i + 1 には人が座っていない

制約

  • N は 1 以上 2 \times 10^5 以下の整数
  • S は #, . からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ。


入力例 1

6
#.##.#

出力例 1

2

i = 1, 4 が条件を満たすので、答えは 2 です。


入力例 2

1
#

出力例 2

0

入力例 3

9
##.#.#.##

出力例 3

3

Score : 100 points

Problem Statement

There are N seats in a row, numbered 1, 2, \ldots, N.

The state of the seats is given by a string S of length N consisting of # and .. If the i-th character of S is #, it means seat i is occupied; if it is ., seat i is unoccupied.

Find the number of integers i between 1 and N - 2, inclusive, that satisfy the following condition:

  • Seats i and i + 2 are occupied, and seat i + 1 is unoccupied.

Constraints

  • N is an integer satisfying 1 \leq N \leq 2 \times 10^5.
  • S is a string of length N consisting of # and ..

Input

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

N
S

Output

Print the answer.


Sample Input 1

6
#.##.#

Sample Output 1

2

i = 1 and 4 satisfy the condition, so the answer is 2.


Sample Input 2

1
#

Sample Output 2

0

Sample Input 3

9
##.#.#.##

Sample Output 3

3
C - Center Alignment

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字からなる N 個の奇数長の文字列 S_1,S_2,\dots,S_N が与えられます。

S_1,S_2,\dots,S_N のうち最も長いものの長さを m とします。 以下の条件を満たす文字列 T_1,T_2,\dots,T_N を求めてください。

  • 条件:T_i はある非負整数 k について k 個の .、S_i、k 個の . をこの順に結合してできる、長さ m の文字列である。

制約

  • N は 1 以上 100 以下の整数
  • S_i は英小文字からなる長さ 1 以上 99 以下の奇数長の文字列

入力

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

N
S_1
S_2
\vdots
S_N

出力

N 行出力せよ。i\ (1 \leq i \leq N) 行目には T_i を出力せよ。


入力例 1

4
apple
blueberry
coconut
dragonfruit

出力例 1

...apple...
.blueberry.
..coconut..
dragonfruit

m=11 であり、T_1,T_2,T_3,T_4 はそれぞれ k=3,1,2,0 について問題文中の条件を満たしています。


入力例 2

6
abc
d
efghi
jkl
mnopq
r

出力例 2

.abc.
..d..
efghi
.jkl.
mnopq
..r..

Score : 200 points

Problem Statement

You are given N strings S_1,S_2,\dots,S_N of odd lengths consisting of lowercase English letters.

Let m be the length of the longest string among S_1,S_2,\dots,S_N. Find strings T_1,T_2,\dots,T_N satisfying the following condition.

  • Condition: T_i is a string of length m formed by concatenating k copies of ., S_i, and k copies of . in this order, for some non-negative integer k.

Constraints

  • N is an integer between 1 and 100, inclusive.
  • S_i is a string of odd length between 1 and 99, inclusive, consisting of lowercase English letters.

Input

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

N
S_1
S_2
\vdots
S_N

Output

Output N lines. The i-th line (1 \leq i \leq N) should contain T_i.


Sample Input 1

4
apple
blueberry
coconut
dragonfruit

Sample Output 1

...apple...
.blueberry.
..coconut..
dragonfruit

m=11, and T_1,T_2,T_3,T_4 satisfy the condition in the problem statement for k=3,1,2,0, respectively.


Sample Input 2

6
abc
d
efghi
jkl
mnopq
r

Sample Output 2

.abc.
..d..
efghi
.jkl.
mnopq
..r..
D - Yellow and Red Card

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1 から N までの番号がついた N 人の選手がサッカーの試合をします。
選手が反則を犯したとき、その選手には イエローカード と レッドカード のどちらかが提示されます。
以下の条件のうち一方を満たした選手は 退場処分 と呼ばれるペナルティを受けます。

  • イエローカードを累計 2 回提示される。
  • レッドカードを提示される。

なお、退場処分を受けた選手にそれ以降カードが提示されることはありません。

あなたはこの試合を観戦します。はじめ、すべての選手はカードを 1 回も提示されていません。
Q 個のイベントが発生するので、イベントで聞かれる質問に正しく答えてください。
イベントは 3 種類あり、c x (c は 1, 2, 3 のいずれか) という形式で入力から与えられます。イベントの説明は次の通りです。

  • 1 x : 選手 x にイエローカードが提示される。
  • 2 x : 選手 x にレッドカードが提示される。
  • 3 x : あなたは選手 x が退場処分を受けたかを質問される。選手 x が退場処分を受けていれば Yes と、そうでなければ No と答える。

制約

  • 1 \leq N \leq 100
  • 1 \leq Q \leq 100
  • 全てのイベントにおいて 1 \leq x \leq N
  • 3 種類目のイベントは少なくとも 1 個以上存在する
  • すでに退場処分を受けた選手にカードが提示されることはない
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ただし、\text{event}_i は i 番目に発生するイベントを意味する。

N Q
\text{event}_1
\text{event}_2
\vdots
\text{event}_Q

イベントは次の 3 つのいずれかの形式で入力される。

1 x
2 x
3 x

出力

入力で与えられる 3 種類目のイベントの個数を X として、X 行出力せよ。
i 行目には、3 種類目のイベントのうち i 番目のもので聞かれる質問について、選手 x が退場処分を受けていれば Yes を、そうでなければ No を出力せよ。


入力例 1

3 9
3 1
3 2
1 2
2 1
3 1
3 2
1 2
3 2
3 3

出力例 1

No
No
Yes
No
Yes
No

イベントを時系列順にすべて説明すると次の通りです。

1 番目のイベントでは、あなたは選手 1 が退場処分を受けたかを質問されます。選手 1 は退場処分を受けていないので No を出力します。
2 番目のイベントでは、あなたは選手 2 が退場処分を受けたかを質問されます。選手 2 は退場処分を受けていないので No を出力します。
3 番目のイベントでは、選手 2 にイエローカードが提示されます。
4 番目のイベントでは、選手 1 にレッドカードが提示されます。選手 1 は退場処分を受けます。
5 番目のイベントでは、あなたは選手 1 が退場処分を受けたかを質問されます。選手 1 は退場処分を受けたので Yes を出力します。
6 番目のイベントでは、あなたは選手 2 が退場処分を受けたかを質問されます。選手 2 は退場処分を受けていないので No を出力します。
7 番目のイベントでは、選手 2 にイエローカードが提示されます。選手 2 は退場処分を受けます。
8 番目のイベントでは、あなたは選手 2 が退場処分を受けたかを質問されます。選手 2 は退場処分を受けたので Yes を出力します。
9 番目のイベントでは、あなたは選手 3 が退場処分を受けたかを質問されます。選手 3 は退場処分を受けていないので No を出力します。

Score : 200 points

Problem Statement

N players numbered 1 to N will play a soccer game.
When a player commits an offense, that player will receive a yellow card or a red card.
A player who satisfies one of the following conditions will be removed from the game.

  • Accumulates two yellow cards.
  • Receives a red card.

Once a player is removed, that player will no longer receive any cards.

You will watch this game. Initially, the players have not received any cards.
There will be Q events. Correctly answer the questions asked in the events.
There are three kinds of events, which are given in the format c x from the input, where c is 1, 2, or 3. The events are as follows.

  • 1 x: Player x receives a yellow card.
  • 2 x: Player x receives a red card.
  • 3 x: You are asked whether player x has been removed from the game. Answer Yes or No.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq Q \leq 100
  • 1 \leq x \leq N in all events.
  • There is at least one event of the third kind.
  • A player who has been removed will no longer receive any cards.
  • All values in the input are integers.

Input

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

N Q
\text{event}_1
\text{event}_2
\vdots
\text{event}_Q

Each event is in one of the following formats:

1 x
2 x
3 x

Output

Print X lines, where X is the number of events of the third kind in the input.
The i-th line should contain Yes if, for the i-th event of the third kind, player x has been removed from the game, and No otherwise.


Sample Input 1

3 9
3 1
3 2
1 2
2 1
3 1
3 2
1 2
3 2
3 3

Sample Output 1

No
No
Yes
No
Yes
No

Here are all the events in chronological order.

In the 1-st event, you are asked whether player 1 has been removed from the game. Player 1 has not been removed, so you should print No.
In the 2-nd event, you are asked whether player 2 has been removed from the game. Player 2 has not been removed, so you should print No.
In the 3-rd event, player 2 receives a yellow card.
In the 4-th event, player 1 receives a red card and is removed from the game.
In the 5-th event, you are asked whether player 1 has been removed from the game. Player 1 has been removed, so you should print Yes.
In the 6-th event, you are asked whether player 2 has been removed from the game. Player 2 has not been removed, so you should print No.
In the 7-th event, player 2 receives a yellow card and is removed from the game.
In the 8-th event, you are asked whether player 2 has been removed from the game. Player 2 has been removed, so you should print Yes.
In the 9-th event, you are asked whether player 3 has been removed from the game. Player 3 has not been removed, so you should print No.

E - Rotate and Sum Query

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

Q 個のクエリが与えられるので順に処理してください。クエリは 2 種類あり、以下のいずれかの形式で与えられます。

  • 1 c: A の先頭の要素を末尾に移動させる操作を c 回行う。
  • 2 l r: \displaystyle \sum_{i=l}^r A_i の値を出力する。

制約

  • 1\le N\le 2\times 10^5
  • 1\le Q\le 2\times 10^5
  • 1\le A_i \le 10^9
  • 1\le c\le N
  • 1\le l\le r \le N
  • 2 つ目の形式のクエリが 1 つ以上存在する
  • 入力される値は全て整数

入力

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

N Q
A_1 A_2 \ldots A_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

各クエリ \text{query}_i は以下の 2 種類のいずれかの形式で与えられる。

1 c
2 l r

出力

問題文の指示に従って 2 つ目の形式のクエリへの答えを改行区切りで出力せよ。


入力例 1

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

出力例 1

8
9

各クエリは以下のように処理されます。

  • 1 つ目のクエリ: A_1+A_2+A_3=3+1+4=8 なので 8 を出力します。
  • 2 つ目のクエリ: A=(3,1,4,5) が A=(1,4,5,3) に変化します。
  • 3 つ目のクエリ: A_2+A_3=4+5=9 なので 9 を出力します。

入力例 2

5 7
1 2 4 8 16
2 1 5
1 4
1 5
2 1 5
2 2 4
1 1
2 3 3

出力例 2

31
31
7
4

Score : 350 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries in order. There are two types of queries, given in the following formats:

  • 1 c: Perform the operation of moving the first element of A to the end c times.
  • 2 l r: Output the value of \displaystyle \sum_{i=l}^r A_i.

Constraints

  • 1\le N\le 2\times 10^5
  • 1\le Q\le 2\times 10^5
  • 1\le A_i \le 10^9
  • 1\le c\le N
  • 1\le l\le r \le N
  • At least one query of the second type exists.
  • All input values are integers.

Input

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

N Q
A_1 A_2 \ldots A_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Each query \text{query}_i is given in one of the following two formats:

1 c
2 l r

Output

Following the instructions in the problem statement, output the answers to the second type queries, separated by newlines.


Sample Input 1

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

Sample Output 1

8
9

Each query is processed as follows:

  • First query: A_1+A_2+A_3=3+1+4=8, so output 8.
  • Second query: A=(3,1,4,5) changes to A=(1,4,5,3).
  • Third query: A_2+A_3=4+5=9, so output 9.

Sample Input 2

5 7
1 2 4 8 16
2 1 5
1 4
1 5
2 1 5
2 2 4
1 1
2 3 3

Sample Output 2

31
31
7
4
F - Number Place

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

9\times 9 のマス目 A があり、各マスには 1 以上 9 以下の整数が書き込まれています。
具体的には、 A の上から i 行目、左から j 列目のマスには A_{i,j} が書き込まれています。

A が次の条件をすべてみたしているならば Yes を、そうでないならば No を出力してください。

  • A の各行について、その行に含まれる 9 マスには 1 以上 9 以下の整数がちょうど 1 個ずつ書き込まれている。
  • A の各列について、その列に含まれる 9 マスには 1 以上 9 以下の整数がちょうど 1 個ずつ書き込まれている。
  • A の行を上から 3 行ずつ 3 つに分け、同様に列も左から 3 列ずつ 3 つに分ける。 これによって A を 9 つの 3\times 3 のマス目に分けたとき、それぞれの 3\times 3 のマス目には 1 以上 9 以下の整数がちょうど 1 個ずつ書き込まれている。

制約

  • 1\leq A_{i,j}\leq 9
  • 入力はすべて整数

入力

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

A_{1,1} A_{1,2} \ldots A_{1,9}
A_{2,1} A_{2,2} \ldots A_{2,9}
\vdots
A_{9,1} A_{9,2} \ldots A_{9,9}

出力

マス目 A が問題文の条件をすべてみたすならば Yes を、 そうでないならば No を出力せよ。


入力例 1

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8

出力例 1

Yes

マス目 A は次のようになっています。

マス目 A は 3 つの条件をすべてみたしているため、Yes を出力します。


入力例 2

1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8

出力例 2

No

マス目 A は次のようになっています。

例えば左上の 3\times 3 のマス目に注目すると 3 つめの条件をみたしていないことが分かるため、No を出力します。


入力例 3

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6

出力例 3

No

マス目 A は次のようになっています。

例えば一番左の列に注目すると 2 つめの条件をみたしていないことが分かるため、No を出力します。

Score : 250 points

Problem Statement

There is a 9\times 9 grid A, where each cell contains an integer between 1 and 9, inclusive.
Specifically, the cell at the i-th row from the top and j-th column from the left contains A_{i,j}.

If A satisfies all of the following conditions, print Yes. Otherwise, print No.

  • For each row of A, the nine cells in that row contain each integer from 1 to 9 exactly once.
  • For each column of A, the nine cells in that column contain each integer from 1 to 9 exactly once.
  • Divide the rows of A into three groups, each of three rows, from top to bottom, and similarly divide the columns into three groups, each of three columns, from left to right. Each 3\times 3 grid obtained from A in this way contains each integer from 1 to 9 exactly once.

Constraints

  • 1\leq A_{i,j}\leq 9
  • All input values are integers.

Input

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

A_{1,1} A_{1,2} \ldots A_{1,9}
A_{2,1} A_{2,2} \ldots A_{2,9}
\vdots
A_{9,1} A_{9,2} \ldots A_{9,9}

Output

If the grid A satisfies all the conditions in the problem statement, print Yes; otherwise, print No.


Sample Input 1

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8

Sample Output 1

Yes

The grid A is shown below.

The grid A satisfies all three conditions, so print Yes.


Sample Input 2

1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8

Sample Output 2

No

The grid A is shown below.

For example, if you look at the top left 3\times 3 grid, you can see that the third condition is unsatisfied, so print No.


Sample Input 3

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6

Sample Output 3

No

The grid A is shown below.

For example, if you look at the leftmost column, you can see that the second condition is unsatisfied, so print No.

G - Keep Distance

Time Limit: 5 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

整数 N と M が与えられます。

以下の条件をすべて満たす長さ N の整数列 (A_1, A_2, \ldots, A_N) を辞書順にすべて出力してください。

  • 1 \leq A_i
  • 2 以上 N 以下の各整数 i に対して A_{i - 1} + 10 \leq A_i
  • A_N \leq M
数列の辞書順とは

長さ N の数列 S = (S_1, S_2, \ldots, S_N) が長さ N の数列 T = (T_1, T_2, \ldots, T_N) より辞書順で小さいとは、ある整数 1 \leq i \leq N が存在して下記の 2 つがともに成り立つことをいいます。

  • (S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1})
  • S_i が T_i より(数として)小さい。

制約

  • 2 \leq N \leq 12
  • 10N - 9 \leq M \leq 10N
  • 入力される値はすべて整数

入力

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

N M

出力

条件を満たす長さ N の整数列の個数を X として X + 1 行出力せよ。

1 行目には X の値を出力せよ。

i + 1 (1 \leq i \leq X) 行目には条件を満たす整数列のうち辞書順で i 番目に小さいものを空白区切りで出力せよ。


入力例 1

3 23

出力例 1

10
1 11 21
1 11 22
1 11 23
1 12 22
1 12 23
1 13 23
2 12 22
2 12 23
2 13 23
3 13 23

(1, 11, 21), (1, 11, 22), (1, 11, 23), (1, 12, 22), (1, 12, 23), (1, 13, 23), (2, 12, 22), (2, 12, 23), (2, 13, 23), (3, 13, 23) の 10 個の数列が条件を満たします。

Score: 425 points

Problem Statement

You are given integers N and M.

Print all integer sequences (A_1, A_2, \ldots, A_N) of length N that satisfy all of the following conditions, in lexicographical order.

  • 1 \leq A_i
  • A_{i - 1} + 10 \leq A_i for each integer i from 2 through N
  • A_N \leq M
What is lexicographical order?

A sequence S = (S_1, S_2, \ldots, S_N) of length N is smaller in lexicographical order than a sequence T = (T_1, T_2, \ldots, T_N) of length N if and only if there exists an integer 1 \leq i \leq N such that both of the following hold:

  • (S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1})
  • S_i is less than T_i (as a number).

Constraints

  • 2 \leq N \leq 12
  • 10N - 9 \leq M \leq 10N
  • All input values are integers.

Input

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

N M

Output

Let X be the number of integer sequences that satisfy the conditions, and print X + 1 lines.

The first line should contain the value of X.

The (i + 1)-th line (1 \leq i \leq X) should contain the i-th smallest integer sequence in lexicographical order, with elements separated by spaces.


Sample Input 1

3 23

Sample Output 1

10
1 11 21
1 11 22
1 11 23
1 12 22
1 12 23
1 13 23
2 12 22
2 12 23
2 13 23
3 13 23

(1, 11, 21), (1, 11, 22), (1, 11, 23), (1, 12, 22), (1, 12, 23), (1, 13, 23), (2, 12, 22), (2, 12, 23), (2, 13, 23), (3, 13, 23) are the 10 sequences that satisfy the conditions.

H - Wrapping Chocolate

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

高橋君は N 枚のチョコレートを持っています。i 枚目のチョコレートは縦 A_i cm 横 B_i cm の長方形の形をしています。
また、高橋君は M 個の箱を持っています。i 個目の箱は縦 C_i cm 横 D_i cm の長方形の形をしています。

以下の条件を全て満たすように N 枚のチョコレートを全て箱に入れることは可能か判定してください。

  • 1 個の箱に入れることのできるチョコレートの数は、高々 1 個である
  • i 枚目のチョコレートを j 個目の箱に入れるとき、A_i \leq C_j かつ B_i \leq D_j を満たす必要がある(回転は不可)

制約

  • 1 \leq N \leq M \leq 2\times 10^5
  • 1 \leq A_i,B_i,C_i,D_i \leq 10^9
  • 入力は全て整数である

入力

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

N M
A_1 \ldots A_N
B_1 \ldots B_N
C_1 \ldots C_M
D_1 \ldots D_M

出力

N 枚のチョコレートを全て箱に入れることが可能ならば Yes と、不可能ならば No と出力せよ。


入力例 1

2 3
2 4
3 2
8 1 5
2 10 5

出力例 1

Yes

1 枚目のチョコレートを 3 個目の箱に入れて、2 枚目のチョコレートを 1 個目の箱に入れればよいです。


入力例 2

2 2
1 1
2 2
100 1
100 1

出力例 2

No

1 個の箱に入れることのできるチョコレートの数は、高々 1 個です。


入力例 3

1 1
10
100
100
10

出力例 3

No

入力例 4

1 1
10
100
10
100

出力例 4

Yes

Score : 500 points

Problem Statement

Takahashi has N pieces of chocolate. The i-th piece has a rectangular shape with a width of A_i centimeters and a length of B_i centimeters.
He also has M boxes. The i-th box has a rectangular shape with a width of C_i centimeters and a length of D_i centimeters.

Determine whether it is possible to put the N pieces of chocolate in the boxes under the conditions below.

  • A box can contain at most one piece of chocolate.
  • A_i \leq C_j and B_i \leq D_j must hold when putting the i-th piece of chocolate in the j-th box (they cannot be rotated).

Constraints

  • 1 \leq N \leq M \leq 2\times 10^5
  • 1 \leq A_i,B_i,C_i,D_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 \ldots A_N
B_1 \ldots B_N
C_1 \ldots C_M
D_1 \ldots D_M

Output

If it is possible to put the N pieces of chocolate in the boxes, print Yes; otherwise, print No.


Sample Input 1

2 3
2 4
3 2
8 1 5
2 10 5

Sample Output 1

Yes

We can put the first piece of chocolate in the third box and the second piece in the first box.


Sample Input 2

2 2
1 1
2 2
100 1
100 1

Sample Output 2

No

A box can contain at most one piece of chocolate.


Sample Input 3

1 1
10
100
100
10

Sample Output 3

No

Sample Input 4

1 1
10
100
10
100

Sample Output 4

Yes
I - 1122 Subsequence 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

数字からなる文字列 S が与えられます。

以下の条件を全て満たす文字列 T を 1122文字列 と呼びます。(定義は C 問題と同じです。)

  • T は数字からなる空でない文字列
  • |T| は偶数。ここで、 |T| は文字列 T の長さを表す
  • T の 1 文字目から \frac{|T|}2 文字目までは全て同じ数字である
  • T の \frac{|T|}2+1 文字目から |T| 文字目までは全て同じ数字である
  • T の 1 文字目の数字に 1 を足すと |T| 文字目の数字になる

例えば 1122 や 01 、 444555 などは 1122文字列 ですが、 1222 や 90 は 1122文字列 ではありません。

S の (連続でなくても良い)部分列 であって 1122文字列 であるものの個数を 998244353 で割ったあまりを求めてください。

ただし、ある二つの部分列が文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えるものとします。

制約

  • S は長さ 1 以上 10^6 以下の数字からなる文字列

入力

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

S

出力

S の部分列であって 1122文字列 であるものの個数を 998244353 で割ったあまりを出力せよ。


入力例 1

1122

出力例 1

5

以下の 5 つの部分列が条件を満たします。

  • S の 1 文字目と 3 文字目を取り出した 12
  • S の 1 文字目と 4 文字目を取り出した 12
  • S の 2 文字目と 3 文字目を取り出した 12
  • S の 2 文字目と 4 文字目を取り出した 12
  • S の 1 文字目から 4 文字目を取り出した 1122

したがって、 5 を出力してください。

文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えることに注意してください。


入力例 2

2025

出力例 2

0

1122文字列 となる部分列が存在しない場合もあります。


入力例 3

0777468889971

出力例 3

30

Score : 500 points

Problem Statement

You are given a string S consisting of digits.

A string T is called a 1122-string if it satisfies all of the following conditions. (The definition is the same as in Problem C.)

  • T is a non-empty string consisting of digits.
  • |T| is even, where |T| denotes the length of string T.
  • All characters from the 1-st through the \frac{|T|}2-th character of T are the same digit.
  • All characters from the (\frac{|T|}2+1)-th through the |T|-th character of T are the same digit.
  • Adding 1 to the digit of the 1-st character of T gives the digit of the |T|-th character.

For example, 1122, 01, and 444555 are 1122-strings, but 1222 and 90 are not 1122-strings.

Find the number, modulo 998244353, of (not necessarily contiguous) subsequences of S that are 1122-strings.

Two subsequences are counted separately if they are extracted from different positions, even if they are identical as strings.

Constraints

  • S is a string consisting of digits with length between 1 and 10^6, inclusive.

Input

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

S

Output

Output the number, modulo 998244353, of subsequences of S that are 1122-strings.


Sample Input 1

1122

Sample Output 1

5

The following five subsequences satisfy the condition.

  • 12 extracted from the 1-st and 3-rd characters of S
  • 12 extracted from the 1-st and 4-th characters of S
  • 12 extracted from the 2-nd and 3-rd characters of S
  • 12 extracted from the 2-nd and 4-th characters of S
  • 1122 extracted from the 1-st through 4-th characters of S

Thus, output 5.

Note that two subsequences are counted separately if they are extracted from different positions, even if they are identical as strings.


Sample Input 2

2025

Sample Output 2

0

There may be no subsequence that is a 1122-string.


Sample Input 3

0777468889971

Sample Output 3

30