A - Filter

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

長さ N の整数列 A=(A _ 1,A _ 2,\ldots,A _ N) が与えられます。

A から偶数だけすべて取り出し、もとの順番を保って出力してください。

制約

  • 1\leq N\leq 100
  • 1\leq A _ i\leq 100\ (1\leq i\leq N)
  • A には 1 つ以上偶数が含まれる
  • 入力はすべて整数

入力

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

N
A _ 1 A _ 2 \ldots A _ N

出力

A から偶数を取り出した列を、空白区切りで 1 行に出力せよ。

入力例 1

5
1 2 3 5 6

出力例 1

2 6

A=(1,2,3,5,6) です。 このうち偶数なのは A _ 2=2,A _ 5=6 の 2 つなので、2 と 6 をこの順に空白区切りで出力してください。

入力例 2

5
2 2 2 3 3

出力例 2

2 2 2

A の中には同じ要素がある場合もあります。

入力例 3

10
22 3 17 8 30 15 12 14 11 17

出力例 3

22 8 30 12 14

Score : 100 points

Problem Statement

You are given a sequence of N integers: A=(A _ 1,A _ 2,\ldots,A _ N).

Print all even numbers in A without changing the order.

Constraints

  • 1\leq N\leq 100
  • 1\leq A _ i\leq 100\ (1\leq i\leq N)
  • A contains at least one even number.
  • 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

Output

Print a line containing the sequence of all even numbers in A, with spaces in between.

Sample Input 1

5
1 2 3 5 6

Sample Output 1

2 6

We have A=(1,2,3,5,6). Among them are two even numbers, A _ 2=2 and A _ 5=6, so print 2 and 6 in this order, with a space in between.

Sample Input 2

5
2 2 2 3 3

Sample Output 2

2 2 2

A may contain equal elements.

Sample Input 3

10
22 3 17 8 30 15 12 14 11 17

Sample Output 3

22 8 30 12 14
B - ASCII Art

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

0 以上 26 以下の整数からなる H 行 W 列の行列 A が与えられます。A の上から i 行目、左から j 列目の要素は A_{i,j} です。

H 個の長さ W の文字列 S_1, S_2, \dots, S_H を次の条件を満たすように定めます。

  • S_i の j 文字目は、 A_{i,j} が 0 ならばピリオド (.)、そうでなければ A_{i,j} 番目の大文字アルファベットである。

S_1, S_2, \dots, S_H を順に出力してください。

制約

  • 1 \leq H \leq 100
  • 1 \leq W \leq 100
  • 0 \leq A_{i,j} \leq 26
  • 入力される値はすべて整数

入力

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

H W
A_{1,1} A_{1,2} \dots A_{1,W}
A_{2,1} A_{2,2} \dots A_{2,W}
\vdots
A_{H,1} A_{H,2} \dots A_{H,W}

出力

H 行出力せよ。i 行目には S_i を出力せよ。

入力例 1

2 3
0 1 2
0 0 3

出力例 1

.AB
..C

S_1 = .AB、S_2 = ..C です。この 2 つを順に出力します。

入力例 2

3 3
24 0 0
0 25 0
0 0 26

出力例 2

X..
.Y.
..Z

入力例 3

3 1
2
9
4

出力例 3

B
I
D

入力例 4

24 60
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 2 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 0 0 0 0 0 0 0 0 0 13 13 14 0 0 0 10 0 0 0 0 0 15 24 14 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 0 0 0 0 0 0 13 23 7 25 24 13 10 0 10 12 0 0 0 0 19 9 23 0 0 0 0 10 10 14 0 0 0 10 14 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 9 13 5 0 0 23 11 14 14 0 0 12 9 1 21 19 0 0 9 12 10 25 3 10 6 0 0 9 13 23 24 14 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 13 14 6 0 0 0 10 5 25 13 0 0 25 0 0 0 0 0 0 0 0 0 0 10 16 0 0 13 21 13 13 14 23 14 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 13 8 2 0 0 0 0 0 13 11 13 19 0 0 1 2 5 9 12 12 5 9 9 20 6 0 14 14 14 9 0 0 0 14 14 18 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 23 13 13 13 13 13 13 14 14 14 13 14 14 13 7 0 0 0 0 0 0 0 0 0 0 0 0 13 13 13 2 0 0 0 0 13 11 13 16 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 13 1 0 0 0 9 20 9 20 20 20 20 13 20 20 13 20 23 8 8 8 20 8 20 7 8 17 7 10 13 14 13 19 0 0 0 0 0 22 14 25 13 16 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 13 9 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 20 20 20 13 13 7 20 26 13 8 6 14 0 0 0 0 0 0 0 0 0
0 0 0 0 0 5 0 0 0 0 0 0 0 1 2 20 20 23 13 2 7 2 10 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 23 13 0 0 0 0 0 0 0 0 0
0 0 0 0 13 0 0 0 0 0 0 0 0 1 0 0 0 13 12 9 14 13 13 9 9 20 12 0 0 0 0 0 0 0 0 0 0 0 1 9 9 9 9 12 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0 0 0 0 19 0 0 14 13 14 14 13 13 0 0 9 5 16 0 0 0 0 0 0 5 20 20 13 2 2 20 9 13 14 14 20 12 12 0 0 0 0 9 13 0 0 0 0 0 0
0 0 1 9 0 0 0 0 0 0 0 0 0 0 0 13 10 13 13 13 13 2 5 12 10 5 0 0 0 0 0 0 0 0 20 16 0 0 0 13 14 13 13 13 13 0 0 10 8 0 0 0 0 0 20 7 0 0 0 0
0 0 4 2 0 0 0 0 0 0 0 0 0 0 0 0 9 7 14 10 10 14 13 5 0 0 0 0 0 0 0 0 0 0 0 23 13 12 13 13 13 13 13 9 13 0 14 4 0 0 0 0 0 0 0 9 16 0 0 0
0 0 22 13 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 20 13 13 13 2 9 14 2 20 14 0 0 0 0 0 0 0 0 0 2 0 0 0
0 0 0 5 13 0 0 0 2 7 13 13 13 13 13 13 13 2 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 20 9 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0
0 0 0 0 20 13 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 14 7 2 20 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 6 0 0 0
0 0 0 0 0 0 9 14 14 0 0 20 20 13 13 20 13 9 0 0 10 0 0 0 0 0 0 9 23 13 9 0 0 0 0 0 0 0 10 6 0 0 7 0 0 9 20 13 13 14 2 0 0 0 0 5 0 0 0 0
0 0 0 0 0 0 0 0 20 13 14 0 0 0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 13 11 0 0 0 0 0 0 0 14 9 0 0 0 20 25 14 7 0 0 0 0 9 1 14 7 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 9 13 13 20 0 0 0 0 0 9 12 0 0 0 0 0 0 0 14 13 14 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 9 20 14 14 4 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 2 9 0 0 0 0 9 9 20 21 7 13 20 0 0 20 23 7 7 2 12 7 6 0 0 0 0 0 0 0 0 0 0 0 0 5 5 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 20 20 9 9 20 24 10 12 10 0 0 0 0 0 0 0 0 20 20 0 0 0 0 0 20 7 7 13 22 2 5 9 2 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 9 20 5 20 5 2 5 7 20 5 14 14 5 11 5 2 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 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 0 0 0 0 0

出力例 4

................................B...........................
...................MMN...J.....OXN..........................
.................MWGYXMJ.JL....SIW....JJN...JN..............
...............IME..WKNN..LIAUS..ILJYCJF..IMWXN.............
..............MNF...JEYM..Y..........JP..MUMMNWN............
.............MHB.....MKMS..ABEILLEIITF.NNNI...NNR...........
..........JWMMMMMMNNNMNNMG............MMMB....MKMP..........
........MA...ITITTTTMTTMTWHHHTHTGHQGJMNMS.....VNYMP.........
......MI...............................TTTMMGTZMHFN.........
.....E.......ABTTWMBGBJL.......................TTWM.........
....M........A...MLINMMIITL...........AIIIIL.......T........
...B..........S..NMNNMM..IEP......ETTMBBTIMNNTLL....IM......
..AI...........MJMMMMBELJE........TP...MNMMMM..JH.....TG....
..DB............IGNJJNME...........WMLMMMMMIM.ND.......IP...
..VM.................................TMMMBINBTN.........B...
...EM...BGMMMMMMMBI....................ITTI.............S...
....TML..................UNGBTX........................IF...
......INN..TTMMTMI..J......IWMI.......JF..G..ITMMNB....E....
........TMN........MI........MK.......NI...TYNG....IANG.....
..........IMMT.....IL.......NMN.......F........IITNNDN......
..............TBI....IITUGMT..TWGGBLGF............EE........
.................TTIITXJLJ........TT.....TGGMVBEIB..........
.........................ITETEBEGTENNEKEB...................
............................................................

Score : 200 points

Problem Statement

You are given an H-by-W matrix A consisting of integers between 0 and 26. The element at the i-th row from the top and j-th column from the left is A_{i,j}.

Let S_1, S_2, \dots, S_H be H strings of length W that satisfy the following.

  • The j-th character of S_i is a period (.) if A_{i,j} is 0, and the A_{i,j}-th uppercase English letter otherwise. (For instance, the 4-th letter is D.)

Print S_1, S_2, \dots, S_H in order.

Constraints

  • 1 \leq H \leq 100
  • 1 \leq W \leq 100
  • 0 \leq A_{i,j} \leq 26
  • All values in the input are integers.

Input

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

H W
A_{1,1} A_{1,2} \dots A_{1,W}
A_{2,1} A_{2,2} \dots A_{2,W}
\vdots
A_{H,1} A_{H,2} \dots A_{H,W}

Output

Print H lines. The i-th line should contain S_i.

Sample Input 1

2 3
0 1 2
0 0 3

Sample Output 1

.AB
..C

We have S_1 = .AB and S_2 = ..C. Print these in order.

Sample Input 2

3 3
24 0 0
0 25 0
0 0 26

Sample Output 2

X..
.Y.
..Z

Sample Input 3

3 1
2
9
4

Sample Output 3

B
I
D

Sample Input 4

24 60
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 2 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 0 0 0 0 0 0 0 0 0 13 13 14 0 0 0 10 0 0 0 0 0 15 24 14 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 0 0 0 0 0 0 13 23 7 25 24 13 10 0 10 12 0 0 0 0 19 9 23 0 0 0 0 10 10 14 0 0 0 10 14 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 9 13 5 0 0 23 11 14 14 0 0 12 9 1 21 19 0 0 9 12 10 25 3 10 6 0 0 9 13 23 24 14 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 13 14 6 0 0 0 10 5 25 13 0 0 25 0 0 0 0 0 0 0 0 0 0 10 16 0 0 13 21 13 13 14 23 14 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 13 8 2 0 0 0 0 0 13 11 13 19 0 0 1 2 5 9 12 12 5 9 9 20 6 0 14 14 14 9 0 0 0 14 14 18 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 23 13 13 13 13 13 13 14 14 14 13 14 14 13 7 0 0 0 0 0 0 0 0 0 0 0 0 13 13 13 2 0 0 0 0 13 11 13 16 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 13 1 0 0 0 9 20 9 20 20 20 20 13 20 20 13 20 23 8 8 8 20 8 20 7 8 17 7 10 13 14 13 19 0 0 0 0 0 22 14 25 13 16 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 13 9 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 20 20 20 13 13 7 20 26 13 8 6 14 0 0 0 0 0 0 0 0 0
0 0 0 0 0 5 0 0 0 0 0 0 0 1 2 20 20 23 13 2 7 2 10 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 23 13 0 0 0 0 0 0 0 0 0
0 0 0 0 13 0 0 0 0 0 0 0 0 1 0 0 0 13 12 9 14 13 13 9 9 20 12 0 0 0 0 0 0 0 0 0 0 0 1 9 9 9 9 12 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0 0 0 0 19 0 0 14 13 14 14 13 13 0 0 9 5 16 0 0 0 0 0 0 5 20 20 13 2 2 20 9 13 14 14 20 12 12 0 0 0 0 9 13 0 0 0 0 0 0
0 0 1 9 0 0 0 0 0 0 0 0 0 0 0 13 10 13 13 13 13 2 5 12 10 5 0 0 0 0 0 0 0 0 20 16 0 0 0 13 14 13 13 13 13 0 0 10 8 0 0 0 0 0 20 7 0 0 0 0
0 0 4 2 0 0 0 0 0 0 0 0 0 0 0 0 9 7 14 10 10 14 13 5 0 0 0 0 0 0 0 0 0 0 0 23 13 12 13 13 13 13 13 9 13 0 14 4 0 0 0 0 0 0 0 9 16 0 0 0
0 0 22 13 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 20 13 13 13 2 9 14 2 20 14 0 0 0 0 0 0 0 0 0 2 0 0 0
0 0 0 5 13 0 0 0 2 7 13 13 13 13 13 13 13 2 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 20 9 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0
0 0 0 0 20 13 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 14 7 2 20 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 6 0 0 0
0 0 0 0 0 0 9 14 14 0 0 20 20 13 13 20 13 9 0 0 10 0 0 0 0 0 0 9 23 13 9 0 0 0 0 0 0 0 10 6 0 0 7 0 0 9 20 13 13 14 2 0 0 0 0 5 0 0 0 0
0 0 0 0 0 0 0 0 20 13 14 0 0 0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 13 11 0 0 0 0 0 0 0 14 9 0 0 0 20 25 14 7 0 0 0 0 9 1 14 7 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 9 13 13 20 0 0 0 0 0 9 12 0 0 0 0 0 0 0 14 13 14 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 9 20 14 14 4 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 2 9 0 0 0 0 9 9 20 21 7 13 20 0 0 20 23 7 7 2 12 7 6 0 0 0 0 0 0 0 0 0 0 0 0 5 5 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 20 20 9 9 20 24 10 12 10 0 0 0 0 0 0 0 0 20 20 0 0 0 0 0 20 7 7 13 22 2 5 9 2 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 9 20 5 20 5 2 5 7 20 5 14 14 5 11 5 2 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 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 0 0 0 0 0

Sample Output 4

................................B...........................
...................MMN...J.....OXN..........................
.................MWGYXMJ.JL....SIW....JJN...JN..............
...............IME..WKNN..LIAUS..ILJYCJF..IMWXN.............
..............MNF...JEYM..Y..........JP..MUMMNWN............
.............MHB.....MKMS..ABEILLEIITF.NNNI...NNR...........
..........JWMMMMMMNNNMNNMG............MMMB....MKMP..........
........MA...ITITTTTMTTMTWHHHTHTGHQGJMNMS.....VNYMP.........
......MI...............................TTTMMGTZMHFN.........
.....E.......ABTTWMBGBJL.......................TTWM.........
....M........A...MLINMMIITL...........AIIIIL.......T........
...B..........S..NMNNMM..IEP......ETTMBBTIMNNTLL....IM......
..AI...........MJMMMMBELJE........TP...MNMMMM..JH.....TG....
..DB............IGNJJNME...........WMLMMMMMIM.ND.......IP...
..VM.................................TMMMBINBTN.........B...
...EM...BGMMMMMMMBI....................ITTI.............S...
....TML..................UNGBTX........................IF...
......INN..TTMMTMI..J......IWMI.......JF..G..ITMMNB....E....
........TMN........MI........MK.......NI...TYNG....IANG.....
..........IMMT.....IL.......NMN.......F........IITNNDN......
..............TBI....IITUGMT..TWGGBLGF............EE........
.................TTIITXJLJ........TT.....TGGMVBEIB..........
.........................ITETEBEGTENNEKEB...................
............................................................
C - Merge Sequences

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

長さ N の狭義単調増加列 A=(A _ 1,A _ 2,\ldots,A _ N) と、長さ M の狭義単調増加列 B=(B _ 1,B _ 2,\ldots,B _ M) が与えられます。 ここで、すべての i,j\ (1\leq i\leq N,1\leq j\leq M) について A _ i\neq B _ j が成り立っています。

長さ N+M の狭義単調増加列 C=(C _ 1,C _ 2,\ldots,C _ {N+M}) を、次の操作を行った結果得られる列として定めます。

  • C を A と B を連結した列とする。厳密には、i=1,2,\ldots,N について C _ i=A _ i とし、i=N+1,N+2,\ldots,N+M について C _ i=B _ {i-N} とする。
  • C を昇順にソートする。

A _ 1,A _ 2,\ldots,A _ N と B _ 1,B _ 2,\ldots,B _ M がそれぞれ C では何番目にあるか求めてください。 より厳密には、まず i=1,2,\ldots,N について C _ k=A _ i を満たす k を順に求めたのち、j=1,2,\ldots,M について C _ k=B _ j を満たす k を順に求めてください。

制約

  • 1\leq N,M\leq 10^5
  • 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
  • 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
  • すべての i,j\ (1\leq i\leq N,1\leq j\leq M) について A _ i\neq B _ j
  • 入力はすべて整数

入力

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

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

出力

答えを 2 行で出力せよ。
1 行目には A _ 1,A _ 2,\ldots,A _ N がそれぞれ C では何番目にあるかを空白区切りで出力せよ。
2 行目には B _ 1,B _ 2,\ldots,B _ M がそれぞれ C では何番目にあるかを空白区切りで出力せよ。

入力例 1

4 3
3 14 15 92
6 53 58

出力例 1

1 3 4 7
2 5 6

C は (3,6,14,15,53,58,92) となります。 A=(3,14,15,92) の要素はそれぞれ 1,3,4,7 番目にあり、B=(6,53,58) の要素はそれぞれ 2,5,6 番目にあります。

入力例 2

4 4
1 2 3 4
100 200 300 400

出力例 2

1 2 3 4
5 6 7 8

入力例 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

出力例 3

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

Score : 300 points

Problem Statement

You are given strictly increasing sequences of length N and M: A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ M). Here, A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).

Let C=(C _ 1,C _ 2,\ldots,C _ {N+M}) be a strictly increasing sequence of length N+M that results from the following procedure.

  • Let C be the concatenation of A and B. Formally, let C _ i=A _ i for i=1,2,\ldots,N, and C _ i=B _ {i-N} for i=N+1,N+2,\ldots,N+M.
  • Sort C in ascending order.

For each of A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M, find its position in C. More formally, for each i=1,2,\ldots,N, find k such that C _ k=A _ i, and for each j=1,2,\ldots,M, find k such that C _ k=B _ j.

Constraints

  • 1\leq N,M\leq 10^5
  • 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
  • 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
  • A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).
  • 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 \ldots A _ N
B _ 1 B _ 2 \ldots B _ M

Output

Print the answer in two lines.
The first line should contain the positions of A _ 1,A _ 2,\ldots,A _ N in C, with spaces in between.
The second line should contain the positions of B _ 1,B _ 2,\ldots,B _ M in C, with spaces in between.

Sample Input 1

4 3
3 14 15 92
6 53 58

Sample Output 1

1 3 4 7
2 5 6

C will be (3,6,14,15,53,58,92). Here, the 1-st, 3-rd, 4-th, 7-th elements are from A=(3,14,15,92), and the 2-nd, 5-th, 6-th elements are from B=(6,53,58).

Sample Input 2

4 4
1 2 3 4
100 200 300 400

Sample Output 2

1 2 3 4
5 6 7 8

Sample Input 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

Sample Output 3

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

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

銀行に人 1, 人 2, \dots, 人 N が並んでいます。
Q 個のイベントが発生します。イベントは次の 3 種類のいずれかです。

  • 1 : 受付に呼ばれていない人のうち、最も小さい番号の人が受付に呼ばれる。
  • 2 x : 人 x が初めて受付に行く。(ここで、人 x はすでに 1 回以上受付に呼ばれている。)
  • 3 : すでに受付に呼ばれているが受付に行っていない人のうち、最も小さい番号の人が再度呼ばれる。

3 種類目のイベントで受付に呼ばれる人の番号を呼ばれた順に出力してください。

制約

  • 1 \leq N \leq 5 \times 10^5
  • 2 \leq Q \leq 5 \times 10^5
  • 全ての人が 1 回以上呼ばれているときに 1 種類目のイベントが発生することはない
  • 2 種類目のイベントについて、人 x はすでに 1 回以上受付に呼ばれている
  • 2 種類目のイベントについて、人 x が 2 回以上受付に行くことはない
  • 呼ばれている人が全員すでに受付に行っているときに 3 種類目のイベントが発生することはない
  • 3 種類目のイベントは少なくとも 1 回発生する
  • 入力される値はすべて整数

入力

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

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

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

1

2 x

3

出力

入力で与えられる 3 種類目のイベントの個数を X として、X 行出力せよ。
i 行目には、3 種類目のイベントのうち i 番目のもので呼ばれた人の番号を出力せよ。

入力例 1

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

出力例 1

1
2
4

i = 1, 2, \dots, Q について、i 番目のイベントが起こる前の時点での、受付に呼ばれたが受付に行っていない人の集合を列挙すると次のようになります。

  • i=1 : \lbrace \rbrace
  • i=2 : \lbrace 1\rbrace
  • i=3 : \lbrace 1,2\rbrace
  • i=4 : \lbrace 1,2\rbrace
  • i=5 : \lbrace 2\rbrace
  • i=6 : \lbrace 2,3\rbrace
  • i=7 : \lbrace 2\rbrace
  • i=8 : \lbrace 2\rbrace
  • i=9 : \lbrace 2,4\rbrace
  • i=10 : \lbrace 4\rbrace

3 種類目のイベントは i=3,7,10 のときに発生しているので、その時点での集合のうち番号が最小の人である 1, 2, 4 を出力します。

Score : 400 points

Problem Statement

N people, with ID numbers 1, 2, \dots, N, are lining up in front of a bank.
There will be Q events. The following three kinds of events can happen.

  • 1 : The teller calls the person with the smallest ID number who has not been called.
  • 2 x : The person with the ID number x comes to the teller for the first time. (Here, person x has already been called by the teller at least once.)
  • 3 : The teller again calls the person with the smallest ID number who has already been called but has not come.

Print the ID numbers of the people called by the teller in events of the third kind.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 2 \leq Q \leq 5 \times 10^5
  • There will not be an event of the first kind when all people have already been called at least once.
  • For each event of the second kind, the person with the ID number x has already been called by the teller at least once.
  • For each event of the second kind, the person with the ID number x will not come to the teller more than once.
  • There will not be an event of the third kind when all people who have already been called have come to the teller.
  • There is at least one event of the third kind.
  • 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

The description of each event is in one of the following formats:

1

2 x

3

Output

Print X lines, where X is the number of events of the third kind.
The i-th line should contain the ID number of the person called in the i-th event of the third kind.

Sample Input 1

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

Sample Output 1

1
2
4

For each i = 1, 2, \dots, Q, shown below is the set of people who have already been called but have not come just before the i-th event.

  • i=1 : \lbrace \rbrace
  • i=2 : \lbrace 1\rbrace
  • i=3 : \lbrace 1,2\rbrace
  • i=4 : \lbrace 1,2\rbrace
  • i=5 : \lbrace 2\rbrace
  • i=6 : \lbrace 2,3\rbrace
  • i=7 : \lbrace 2\rbrace
  • i=8 : \lbrace 2\rbrace
  • i=9 : \lbrace 2,4\rbrace
  • i=10 : \lbrace 4\rbrace

The events for i=3,7,10 are of the third kind, so you should print the persons with the smallest ID numbers in the sets for those events: 1, 2, 4.
E - 2xN Grid

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

2 行 L 列のマス目があります。 上から i 行目 (i\in\lbrace1,2\rbrace)、左から j 列目 (1\leq j\leq L)のマス目を (i,j) で表します。 (i,j) には整数 x _ {i,j} が書かれています。

x _ {1,j}=x _ {2,j} であるような整数 j の個数を求めてください。

ただし、x _ {i,j} の情報は (x _ {1,1},x _ {1,2},\ldots,x _ {1,L}) と (x _ {2,1},x _ {2,2},\ldots,x _ {2,L}) をそれぞれ連長圧縮した、長さ N _ 1 の列 ((v _ {1,1},l _ {1,1}),\ldots,(v _ {1,N _ 1},l _ {1,N _ 1})) と長さ N _ 2 の列 ((v _ {2,1},l _ {2,1}),\ldots,(v _ {2,N _ 2},l _ {2,N _ 2})) として与えられます。

ここで、列 A の連長圧縮とは、A の要素 v _ i と正整数 l _ i の組 (v _ i,l _ i) の列であって、次の操作で得られるものです。

  1. A を異なる要素が隣り合っている部分で分割する。
  2. 分割した各列 B _ 1,B _ 2,\ldots,B _ k に対して、v _ i を B _ i の要素、l _ i を B _ i の長さとする。

制約

  • 1\leq L\leq 10 ^ {12}
  • 1\leq N _ 1,N _ 2\leq 10 ^ 5
  • 1\leq v _ {i,j}\leq 10 ^ 9\ (i\in\lbrace1,2\rbrace,1\leq j\leq N _ i)
  • 1\leq l _ {i,j}\leq L\ (i\in\lbrace1,2\rbrace,1\leq j\leq N _ i)
  • v _ {i,j}\neq v _ {i,j+1}\ (i\in\lbrace1,2\rbrace,1\leq j\lt N _ i)
  • l _ {i,1}+l _ {i,2}+\cdots+l _ {i,N _ i}=L\ (i\in\lbrace1,2\rbrace)
  • 入力はすべて整数

入力

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

L N _ 1 N _ 2
v _ {1,1} l _ {1,1}
v _ {1,2} l _ {1,2}
\vdots
v _ {1,N _ 1} l _ {1,N _ 1}
v _ {2,1} l _ {2,1}
v _ {2,2} l _ {2,2}
\vdots
v _ {2,N _ 2} l _ {2,N _ 2}

出力

答えを 1 行で出力せよ。

入力例 1

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

出力例 1

4

マス目は以下の図のようになっています。

x _ {1,j}=x _ {2,j} となるような整数 j は、j=1,2,5,8 の 4 つなので、出力すべき値は 4 です。

入力例 2

10000000000 1 1
1 10000000000
1 10000000000

出力例 2

10000000000

答えが 32\operatorname{bit} 整数に収まらない場合があることに注意してください。

入力例 3

1000 4 7
19 79
33 463
19 178
33 280
19 255
33 92
34 25
19 96
12 11
19 490
33 31

出力例 3

380

Score : 500 points

Problem Statement

We have a grid with 2 rows and L columns. Let (i,j) denote the square at the i-th row from the top (i\in\lbrace1,2\rbrace) and j-th column from the left (1\leq j\leq L). (i,j) has an integer x _ {i,j} written on it.

Find the number of integers j such that x _ {1,j}=x _ {2,j}.

Here, the description of x _ {i,j} is given to you as the run-length compressions of (x _ {1,1},x _ {1,2},\ldots,x _ {1,L}) and (x _ {2,1},x _ {2,2},\ldots,x _ {2,L}) into sequences of lengths N _ 1 and N _ 2, respectively: ((v _ {1,1},l _ {1,1}),\ldots,(v _ {1,N _ 1},l _ {1,N _ 1})) and ((v _ {2,1},l _ {2,1}),\ldots,(v _ {2,N _ 2},l _ {2,N _ 2})).

Here, the run-length compression of a sequence A is a sequence of pairs (v _ i,l _ i) of an element v _ i of A and a positive integer l _ i obtained as follows.

  1. Split A between each pair of different adjacent elements.
  2. For each sequence B _ 1,B _ 2,\ldots,B _ k after the split, let v _ i be the element of B _ i and l _ i be the length of B _ i.

Constraints

  • 1\leq L\leq 10 ^ {12}
  • 1\leq N _ 1,N _ 2\leq 10 ^ 5
  • 1\leq v _ {i,j}\leq 10 ^ 9\ (i\in\lbrace1,2\rbrace,1\leq j\leq N _ i)
  • 1\leq l _ {i,j}\leq L\ (i\in\lbrace1,2\rbrace,1\leq j\leq N _ i)
  • v _ {i,j}\neq v _ {i,j+1}\ (i\in\lbrace1,2\rbrace,1\leq j\lt N _ i)
  • l _ {i,1}+l _ {i,2}+\cdots+l _ {i,N _ i}=L\ (i\in\lbrace1,2\rbrace)
  • All values in the input are integers.

Input

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

L N _ 1 N _ 2
v _ {1,1} l _ {1,1}
v _ {1,2} l _ {1,2}
\vdots
v _ {1,N _ 1} l _ {1,N _ 1}
v _ {2,1} l _ {2,1}
v _ {2,2} l _ {2,2}
\vdots
v _ {2,N _ 2} l _ {2,N _ 2}

Output

Print a single line containing the answer.

Sample Input 1

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

Sample Output 1

4

The grid is shown below.

We have four integers j such that x _ {1,j}=x _ {2,j}: j=1,2,5,8. Thus, you should print 4.

Sample Input 2

10000000000 1 1
1 10000000000
1 10000000000

Sample Output 2

10000000000

Note that the answer may not fit into a 32-bit integer.

Sample Input 3

1000 4 7
19 79
33 463
19 178
33 280
19 255
33 92
34 25
19 96
12 11
19 490
33 31

Sample Output 3

380
F - Sugar Water 2

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

高橋君は N 本の砂糖水を、青木君は M 本の砂糖水を持っています。
高橋君の持っている i 番目の砂糖水は砂糖 A_i グラムと水 B_i グラムからなります。
青木君の持っている i 番目の砂糖水は砂糖 C_i グラムと水 D_i グラムからなります。
2 人の持つ砂糖水をそれぞれ 1 本ずつ選んで混ぜる方法は NM 通りあります。そのような方法でできる砂糖水の中で、濃度が高い方から K 番目の砂糖水の濃度が何 \% であるかを求めてください。
ここで、砂糖 x グラムと水 y グラムからなる砂糖水の濃度は \dfrac{100x}{x+y}\ \% です。また、砂糖が溶け残ることは考えないものとします。

制約

  • 1 \leq N, M \leq 5 \times 10^4
  • 1 \leq K \leq N \times M
  • 1 \leq A_i, B_i, C_i, D_i \leq 10^5
  • 入力される値はすべて整数

入力

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

N M K
A_1 B_1
A_2 B_2
\vdots
A_N B_N
C_1 D_1
C_2 D_2
\vdots
C_M D_M

出力

濃度が高い方から K 番目の砂糖水の濃度をパーセントで出力せよ。
なお、真の値との絶対誤差または相対誤差が 10^{−9} 以下であれば正解として扱われる。

入力例 1

3 1 1
1 2
4 1
1 4
1 4

出力例 1

50.000000000000000

以下では高橋君が持っている i 番目の砂糖水と青木君が持っている j 番目の砂糖水を混ぜてできる砂糖水を (i, j) と表します。
あり得る砂糖水の混ぜ方とその濃度を列挙すると以下のようになります。

  • (1, 1) : 100 \times \frac{1 + 1}{(1 + 1) + (2 + 4)} = 25 \%
  • (2, 1) : 100 \times \frac{1 + 4}{(4 + 1) + (1 + 4)} = 50 \%
  • (3, 1) : 100 \times \frac{1 + 1}{(1 + 1) + (4 + 4)} = 20 \%

この中で濃度が高い方から 1 番目の砂糖水は (2, 1) で、濃度は 50 \% です。

入力例 2

2 2 2
6 4
10 1
5 8
9 6

出力例 2

62.500000000000000

入力例 3

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

出力例 3

54.166666666666664

Score : 500 points

Problem Statement

Takahashi and Aoki have N and M bottles of sugar water, respectively.
Takahashi's i-th sugar water is composed of A_i grams of sugar and B_i grams of water.
Aoki's i-th sugar water is composed of C_i grams of sugar and D_i grams of water.
There are NM ways to choose one from Takahashi's sugar waters and one from Aoki's and mix them. Among the NM sugar waters that can be obtained in this way, find the concentration of sugar in the sugar water with the K-th highest concentration of sugar.
Here, the concentration of sugar in sugar water composed of x grams of sugar and y grams of water is \dfrac{100x}{x+y} percent. We will ignore saturation.

Constraints

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

Input

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

N M K
A_1 B_1
A_2 B_2
\vdots
A_N B_N
C_1 D_1
C_2 D_2
\vdots
C_M D_M

Output

Print the concentration of sugar in the sugar water with the K-th highest concentration of sugar in percent.
Your output will be considered correct if the absolute or relative error from the true value is at most 10^{−9}.

Sample Input 1

3 1 1
1 2
4 1
1 4
1 4

Sample Output 1

50.000000000000000

Let (i, j) denote the sugar water obtained by mixing Takahashi's i-th sugar water and Aoki's j-th.
Below are the sugar waters that can be obtained and their concentrations of sugar.

  • (1, 1) : 100 \times \frac{1 + 1}{(1 + 1) + (2 + 4)} = 25 \%
  • (2, 1) : 100 \times \frac{1 + 4}{(4 + 1) + (1 + 4)} = 50 \%
  • (3, 1) : 100 \times \frac{1 + 1}{(1 + 1) + (4 + 4)} = 20 \%

Among them, the sugar water with the highest concentration of sugar is (2, 1), with a concentration of 50 percent.

Sample Input 2

2 2 2
6 4
10 1
5 8
9 6

Sample Output 2

62.500000000000000

Sample Input 3

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

Sample Output 3

54.166666666666664
G - Distance Queries on a Tree

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点の木 T が与えられます。 辺 i (1\leq i\leq N-1) は頂点 u _ i と v _ i を結んでおり、重みは w _ i です。

次の 2 種類のクエリが合計 Q 個与えられるので、順に処理してください。

  • 1 i w：辺 i の重みを w に変更する。
  • 2 u v：頂点 u と頂点 v の距離を出力する。

ただし、木の 2 頂点 u,v の距離とは、u と v を両端点とするパスに含まれる辺の重みの合計として得られる値のうち最小のものです。

制約

  • 1\leq N\leq 2\times10^5
  • 1\leq u _ i,v _ i\leq N\ (1\leq i\leq N-1)
  • 1\leq w _ i\leq 10^9\ (1\leq i\leq N-1)
  • 与えられるグラフは木
  • 1\leq Q\leq 2\times10^5
  • 1 番目の形式のクエリについて、
    • 1\leq i\leq N-1
    • 1\leq w\leq 10^9
  • 2 番目の形式のクエリについて、
    • 1\leq u,v\leq N
  • 2 番目の形式のクエリが 1 つ以上存在する
  • 入力はすべて整数

入力

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

N
u _ 1 v _ 1 w _ 1
u _ 2 v _ 2 w _ 2
\vdots
u _ {N-1} v _ {N-1} w _ {N-1}
Q
\operatorname{query} _ 1
\operatorname{query} _ 2
\vdots
\operatorname{query} _ Q

ただし、\operatorname{query} _ i は i 個目のクエリを表しており、次の形式のいずれかで与えられる。

1 i w

2 u v

出力

2 番目の形式のクエリの個数を q 個として q 行出力せよ。 j 行目 (1\leq j\leq q) には、2 番目の形式のクエリのうち j 個目のものに対する答えを出力せよ。

入力例 1

5
1 2 3
1 3 6
1 4 9
4 5 10
4
2 2 3
2 1 5
1 3 1
2 1 5

出力例 1

9
19
11

木ははじめ、下の図のようになっています。

各クエリでは、以下のような処理を行います。

  • 1 つめのクエリでは、頂点 2 と頂点 3 の距離を出力します。辺 1 と辺 2 をこの順に使うことで重みの合計が 9 であるようなパスが得られ、これが最小なので 9 を出力します。
  • 2 つめのクエリでは、頂点 1 と頂点 5 の距離を出力します。辺 3 と辺 4 をこの順に使うことで重みの合計が 19 であるようなパスが得られ、これが最小なので 19 を出力します。
  • 3 つめのクエリでは、辺 3 の重みを 1 に変更します。
  • 4 つめのクエリでは、頂点 1 と頂点 5 の距離を出力します。辺 3 と辺 4 をこの順に使うことで重みの合計が 11 であるようなパスが得られ、これが最小なので 11 を出力します。

入力例 2

7
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
3
2 1 6
1 1 294967296
2 1 6

出力例 2

5000000000
4294967296

答えが 32\operatorname{bit} 整数に収まらない場合があることに注意してください。

入力例 3

1
1
2 1 1

出力例 3

0

入力例 4

8
1 2 105
1 3 103
2 4 105
2 5 100
5 6 101
3 7 106
3 8 100
18
2 2 8
2 3 6
1 4 108
2 3 4
2 3 5
2 5 5
2 3 1
2 4 3
1 1 107
2 3 1
2 7 6
2 3 8
2 1 5
2 7 6
2 4 7
2 1 7
2 5 3
2 8 6

出力例 4

308
409
313
316
0
103
313
103
525
100
215
525
421
209
318
519

Score : 600 points

Problem Statement

You are given a tree T with N vertices. Edge i (1\leq i\leq N-1) connects vertices u _ i and v _ i, and has a weight of w _ i.

Process Q queries in order. There are two kinds of queries as follows.

  • 1 i w : Change the weight of edge i to w.
  • 2 u v：Print the distance between vertex u and vertex v.

Here, the distance between two vertices u and v of a tree is the smallest total weight of edges in a path whose endpoints are u and v.

Constraints

  • 1\leq N\leq 2\times10^5
  • 1\leq u _ i,v _ i\leq N\ (1\leq i\leq N-1)
  • 1\leq w _ i\leq 10^9\ (1\leq i\leq N-1)
  • The given graph is a tree.
  • 1\leq Q\leq 2\times10^5
  • For each query of the first kind,
    • 1\leq i\leq N-1, and
    • 1\leq w\leq 10^9.
  • For each query of the second kind,
    • 1\leq u,v\leq N.
  • There is at least one query of the second kind.
  • All values in the input are integers.

Input

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

N
u _ 1 v _ 1 w _ 1
u _ 2 v _ 2 w _ 2
\vdots
u _ {N-1} v _ {N-1} w _ {N-1}
Q
\operatorname{query} _ 1
\operatorname{query} _ 2
\vdots
\operatorname{query} _ Q

Here, \operatorname{query} _ i denotes the i-th query and is in one of the following format:

1 i w

2 u v

Output

Print q lines, where q is the number of queries of the second kind. The j-th line (1\leq j\leq q) should contain the answer to the j-th query of the second kind.

Sample Input 1

5
1 2 3
1 3 6
1 4 9
4 5 10
4
2 2 3
2 1 5
1 3 1
2 1 5

Sample Output 1

9
19
11

The initial tree is shown in the figure below.

Each query should be processed as follows.

  • The first query asks you to print the distance between vertex 2 and vertex 3. Edge 1 and edge 2, in this order, form a path between them with a total weight of 9, which is the minimum, so you should print 9.
  • The second query asks you to print the distance between vertex 1 and vertex 5. Edge 3 and edge 4, in this order, form a path between them with a total weight of 19, which is the minimum, so you should print 19.
  • The third query changes the weight of edge 3 to 1.
  • The fourth query asks you to print the distance between vertex 1 and vertex 5. Edge 3 and edge 4, in this order, form a path between them with a total weight of 11, which is the minimum, so you should print 11.

Sample Input 2

7
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
3
2 1 6
1 1 294967296
2 1 6

Sample Output 2

5000000000
4294967296

Note that the answers may not fit into 32-bit integers.

Sample Input 3

1
1
2 1 1

Sample Output 3

0

Sample Input 4

8
1 2 105
1 3 103
2 4 105
2 5 100
5 6 101
3 7 106
3 8 100
18
2 2 8
2 3 6
1 4 108
2 3 4
2 3 5
2 5 5
2 3 1
2 4 3
1 1 107
2 3 1
2 7 6
2 3 8
2 1 5
2 7 6
2 4 7
2 1 7
2 5 3
2 8 6

Sample Output 4

308
409
313
316
0
103
313
103
525
100
215
525
421
209
318
519
Ex - K-Coloring

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

頂点に 1 から N の、辺に 1 から M の番号がついた N 頂点 M 辺の単純無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結んでいます。

このグラフのそれぞれの頂点に 1 以上 K 以下の整数を書きこむ方法のうち、次の条件を満たす方法の個数を 998244353 で割った余りを求めてください。

  • 辺で結ばれた頂点同士には異なる数が書きこまれている。

制約

  • 1 \leq N \leq 30
  • 0 \leq M \leq \min \left(30, \frac{N(N-1)}{2} \right)
  • 1 \leq K \leq 10^9
  • 1 \leq u_i \lt v_i \leq N
  • 入力で与えられるグラフは単純

入力

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

N M K
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

条件を満たすように頂点に 1 以上 K 以下の整数を書きこむ方法の個数を 998244353 で割った余りを出力せよ。

入力例 1

4 3 2
1 2
2 4
2 3

出力例 1

2

条件を満たす整数の書きこみ方は次の 2 通りです。

  • 頂点 1, 3, 4 に 1 を、頂点 2 に 2 を書きこむ。
  • 頂点 2 に 1 を、頂点 1, 3, 4 に 2 を書きこむ。

入力例 2

4 0 10

出力例 2

10000

10^4 通り全ての書きこみ方が条件を満たします。

入力例 3

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

出力例 3

120

入力例 4

5 6 294
1 2
2 4
1 3
2 3
4 5
3 5

出力例 4

838338733

入力例 5

7 12 1000000000
4 5
2 7
3 4
6 7
3 5
5 6
5 7
1 3
4 7
1 5
2 3
3 6

出力例 5

418104233

Score : 600 points

Problem Statement

You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i.

Find the number, modulo 998244353, of ways to write an integer between 1 and K, inclusive, on each vertex of this graph to satisfy the following condition:

  • two vertices connected by an edge always have different numbers written on them.

Constraints

  • 1 \leq N \leq 30
  • 0 \leq M \leq \min \left(30, \frac{N(N-1)}{2} \right)
  • 1 \leq K \leq 10^9
  • 1 \leq u_i \lt v_i \leq N
  • The given graph is simple.

Input

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

N M K
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print the number, modulo 998244353, of ways to write integers between 1 and K, inclusive, on the vertices to satisfy the condition.

Sample Input 1

4 3 2
1 2
2 4
2 3

Sample Output 1

2

Here are the two ways to satisfy the condition.

  • Write 1 on vertices 1, 3, 4, and write 2 on vertex 2.
  • Write 1 on vertex 2, and write 2 on vertex 1, 3, 4.

Sample Input 2

4 0 10

Sample Output 2

10000

All 10^4 ways satisfy the condition.

Sample Input 3

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

Sample Output 3

120

Sample Input 4

5 6 294
1 2
2 4
1 3
2 3
4 5
3 5

Sample Output 4

838338733

Sample Input 5

7 12 1000000000
4 5
2 7
3 4
6 7
3 5
5 6
5 7
1 3
4 7
1 5
2 3
3 6

Sample Output 5

418104233