Problem Statement

You are given a string ~S~ of length ~12~ . How many occurrences of ZONe s does it contain as contiguous substrings?

Constraints

• ~S~ is a string of length ~12~ consisting of English letters.

Input

Input is given from Standard Input in the following format:

~S~

Output

Print the answer.

Sample Input 1

abcdZONefghi

Sample Output 1

1

The ~5~ -th through ~8~ -th characters of ~S~ form a ZONe .

Sample Input 2

ZONeZONeZONe

Sample Output 2

3

Sample Input 3

helloAtZoner

Sample Output 3

0

The ~8~ -th through ~11~ -th characters of ~S~ form a Zone , which is not a ZONe .

Problem Statement

Snuke has two number sequences ~a~ and ~b~ , each of length ~N~ . The ~i~ -th number of ~a~ is ~a_i~ , and that of ~b~ is ~b_i~ .

Using these sequences, he has decided to make a new sequence ~c~ of length ~N~ . For each ~n~ such that ~1 \leq n \leq N~ , ~c_n~ , the ~n~ -th number of ~c~ , is the maximum value of ~a_i b_j~ for a pair ~(i,j)~ such that ~1 \leq i \leq j \leq n~ . Formally, we have ~c_n = \max_{1 \leq i \leq j \leq n} a_{i}b_{j}~ .

Find ~c_1, c_2, \ldots, c_{N}~ .

Constraints

• All values in input are integers.
• ~1 \leq N \leq 2 \times 10^{5}~
• ~1 \leq a_i, b_i \leq 10^9~

Input

Input is given from Standard Input in the following format:

~N~

~a_{1}~ ~a_{2}~ ~\cdots~ ~a_{N}~

~b_{1}~ ~b_{2}~ ~\cdots~ ~b_{N}~

Print

Print ~N~ lines. The ~n~ -th line from the top should contain ~c_{n}~ .

Sample Input 1

3
3 2 20
1 4 1

Sample Output 1

3
12
20

We have:

• ~c_{1} = \max(a_{1}b_{1}) = 3~ ;
• ~c_{2} = \max(a_{1}b_{1}, a_{1}b_{2},a_{2}b_{2}) = 12~ ;
• ~c_{3} = \max(a_{1}b_{1}, a_{1}b_{2}, a_{1}b_{3}, a_{2}b_{2},a_{2}b_{3},a_{3}b_{3}) = 20~ .

Sample Input 2

20
715806713 926832846 890153850 433619693 890169631 501757984 778692206 816865414 50442173 522507343 546693304 851035714 299040991 474850872 133255173 905287070 763360978 327459319 193289538 140803416
974365976 488724815 821047998 371238977 256373343 218153590 546189624 322430037 131351929 768434809 253508808 935670831 251537597 834352123 337485668 272645651 61421502 439773410 621070911 578006919

Sample Output 2

697457706539596888
697457706539596888
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
760974252688942308
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026
867210459214915026

Problem Statement

Snuke has ~N~ balls, each with an integer written on it. The numbers on the balls are ~a_1, a_2, \ldots, a_N~ .

He has decided to put these ~N~ balls in ~K~ boxes. Every ball must be in some box, but there may be boxes with zero or multiple balls.

After he put the balls in the boxes, the lid of each box will show an integer. Let ~x~ be the integer shown on a box. ~x~ is the minimum non-negative integer such that the box contains no ball with ~x~ . For example, the lid of an empty box will show ~0~ ; the lid of a box with balls ~0, 1, 3, 5~ will show ~2~ ; the lid of a box with balls ~1, 2, 3~ will show ~0~ .

Find the maximum possible sum of the integers the lids show.

Constraints

• All values in input are integers.
• ~1 \leq K \leq N \leq 3 \times 10^{5}~
• ~0 \leq a_i < N~

Input

Input is given from Standard Input in the following format:

~N~ ~K~

~a_1~ ~a_2~ ~\cdots~ ~a_N~

Output

Print the maximum possible sum of the integers the lids show.

Sample Input 1

4 2
0 1 0 2

Sample Output 1

4

• An optimal solution is to allocate the sets of balls ~\\{0,1,2 \\},\\{0\\}~ to the boxes.
• In this case, the lids show ~3, 1~ , respectively, for a total of ~4~ .

Sample Input 2

5 2
0 1 1 2 3

Sample Output 2

4

• An optimal solution is to allocate the (multi)sets of balls ~\\{0,1,1,2,3\\}, \\{\\}~ to the boxes.
• In this case, the lids show ~4, 0~ , respectively, for a total of ~4~ .
• Note that we may have empty boxes.

Sample Input 3

20 4
6 2 6 8 4 5 5 8 4 1 7 8 0 3 6 1 1 8 3 0

Sample Output 3

11

Problem Statement

We have a grid with ~H~ rows and ~W~ columns of squares. Let ~(i, j)~ denote the square at the ~i~ -th row from the top and ~j~ -th column from the left. On each square, we can write a letter: R , D , or X . Initially, every square is empty.

Snuke chose ~K~ of the squares and wrote characters on them. The ~i~ -th square he chose was ~(h_i,w_i)~ , and he wrote the letter ~c_i~ on it.

There are ~3^{HW-K}~ ways to write a letter on each of the remaining squares. Find the sum of the answers to the problem below for all those ~3^{HW-K}~ ways, modulo ~998244353~ .

We have a robot that can walk on the grid. When it is at ~(i,j)~ , it can move to ~(i+1, j)~ or ~(i, j+1)~ .
However, if R is written on ~(i, j)~ , it can only move to ~(i, j+1)~ ; if D is written on ~(i, j)~ , it can only move to ~(i+1, j)~ . If X is written on ~(i, j)~ , both choices are possible.

When the robot is put at ~(1, 1)~ , how many paths can the robot take to reach ~(H, W)~ without going out of the grid? We assume the robot halts when reaching ~(H, W)~ .

Here, we distinguish two paths when the sets of squares traversed by the robot are different.

Constraints

• ~2 \leq H,W \leq 5000~
• ~0 \leq K \leq \min(HW,2 \times 10^5)~
• ~1 \leq h_i \leq H~
• ~1 \leq w_i \leq W~
• ~(h_i,w_i) \neq (h_j,w_j)~ for ~i \neq j~ .
• ~c_i~ is R , D , or X .

Input

Input is given from Standard Input in the following format:

~H~ ~W~ ~K~

~h_1~ ~w_1~ ~c_1~

~\vdots~

~h_K~ ~w_K~ ~c_K~

Output

Print the answer.

Sample Input 1

2 2 3
1 1 X
2 1 R
2 2 R

Sample Output 1

5

• Only ~(1,2)~ is empty.
  • If we write R on it, there is one way that the robot can take to reach ~(H, W)~ .
  • If we write D on it, there are two ways that the robot can take to reach ~(H, W)~ .
  • If we write X on it, there are two ways that the robot can take to reach ~(H, W)~ .
• We should print the sum of these counts: ~5~ .

Sample Input 2

3 3 5
2 3 D
1 3 D
2 1 D
1 2 X
3 1 R

Sample Output 2

150

Sample Input 3

5000 5000 10
585 1323 R
2633 3788 X
1222 4989 D
1456 4841 X
2115 3191 R
2120 4450 X
4325 2864 X
222 3205 D
2134 2388 X
2262 3565 R

Sample Output 3

139923295

• Be sure to compute the sum modulo ~998244353~ .

Problem Statement

You want to choose three persons from ~N~ candidates to form a team.
Each candidate has five parameters: power, speed, technique, knowledge, and inventiveness.
The power, speed, technique, knowledge, and the inventiveness of the ~i~ -th candidate are ~A_i~ , ~B_i~ , ~C_i~ , ~D_i~ , and ~E_i~ , respectively.
Let us define your team's power as the maximum of the members' powers. The team's speed, technique, knowledge, and inventiveness are defined similarly.
Then, let us define your team's total strength as the minimum of the team's power, speed, technique, knowledge, and inventiveness.
Find the maximum possible value of your team's total strength.

Constraints

• All values in input are integers.
• ~3 ≤ N ≤ 3000~
• ~1 ≤ A_i, B_i, C_i, D_i, E_i ≤ 10^9~

Input

Input is given from Standard Input in the following format:

~N~

~A_1~ ~B_1~ ~C_1~ ~D_1~ ~E_1~

~A_2~ ~B_2~ ~C_2~ ~D_2~ ~E_2~

~\vdots~

~A_N~ ~B_N~ ~C_N~ ~D_N~ ~E_N~

Output

Print the answer.

Sample Input 1

3
3 9 6 4 6
6 9 3 1 1
8 8 9 3 7

Sample Output 1

4

We have no choice but to choose all three of them.
Then, the team's parameters will be as follows:

• power: ~\max(3, 6, 8) = 8~ ;
• speed: ~\max(9, 9, 8) = 9~ ;
• technique: ~\max(6, 3, 9) = 9~ ;
• knowledge: ~\max(4, 1, 3) = 4~ ;
• inventiveness: ~\max(6, 1, 7) = 7~ .

Thus, the team's total strength will be ~\min(8, 9, 9, 4, 7) = 4~ .

Sample Input 2

5
6 13 6 19 11
4 4 12 11 18
20 7 19 2 5
15 5 12 20 7
8 7 6 18 5

Sample Output 2

13

If we choose the ~1~ -st, ~2~ -nd, and ~3~ -rd candidates, the team's total strength will be ~\min(20, 13, 19, 19, 18) = 13~ .

Sample Input 3

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

Sample Output 3

10