Problem Statement

N examinees took an entrance exam.
The examinee numbered i scored A_i points in math and B_i points in English.

The admissions are determined as follows.

1. X examinees with the highest math scores are admitted.
2. Then, among the examinees who are not admitted yet, Y examinees with the highest English scores are admitted.
3. Then, among the examinees who are not admitted yet, Z examinees with the highest total scores in math and English are admitted.
4. Those examinees who are not admitted yet are rejected.

Here, in each of the steps 1. to 3., ties are broken by examinees' numbers: an examinee with the smaller examinee's number is prioritized. See also Sample Input and Output.

Print the examinees' numbers of the admitted examinees determined by the steps above in ascending order, separated by newlines.

Constraints

• All values in input are integers.
• 1 \le N \le 1000
• 0 \le X,Y,Z \le N
• 1 \le X+Y+Z \le N
• 0 \le A_i,B_i \le 100

Sample Input 1

6 1 0 2
80 60 80 60 70 70
40 20 50 90 90 80

Sample Output 1

1
4
5

• First, 1 examinee with the highest math score is admitted.
  • Examinee 1 is tied with Examinee 3, scoring the highest 80 points in math, and the tie is broken by the examinees' numbers, so Examinee 1 is admitted.
• Then, among the examinees who are not admitted yet, 0 examinees with the highest English scores are admitted.
  • Obviously, it does not affect the admissions.
• Then, among the examinees who are not admitted yet, 2 examinees with the highest total scores in math and English are admitted.
  • First, among the examinees who are not admitted yet, Examinee 5 is admitted, scoring the highest total score of 160 points.
  • Next, among the examinees who are not admitted yet, Examinee 4 is tied with Examinee 6, scoring a total score of 150 points. The tie is broken by the examinees' numbers, and Examinee 4 is admitted.

Therefore, the examinees' numbers of the admitted examinees are 1, 4, and 5. Print them in ascending order.

Sample Input 2

5 2 1 2
0 100 0 100 0
0 0 100 100 0

Sample Output 2

1
2
3
4
5

All examinees may be admitted.

Sample Input 3

15 4 3 2
30 65 20 95 100 45 70 85 20 35 95 50 40 15 85
0 25 45 35 65 70 80 90 40 55 20 20 45 75 100

Sample Output 3

2
4
5
6
7
8
11
14
15

Problem Statement

There are non-negative integers A, B, C, D, E, and F, which satisfy A\times B\times C\geq D\times E\times F.
Find the remainder when (A\times B\times C)-(D\times E\times F) is divided by 998244353.

Constraints

• 0\leq A,B,C,D,E,F\leq 10^{18}
• A\times B\times C\geq D\times E\times F
• A, B, C, D, E, and F are integers.

Sample Input 1

2 3 5 1 2 4

Sample Output 1

22

Since A\times B\times C=2\times 3\times 5=30 and D\times E\times F=1\times 2\times 4=8,
we have (A\times B\times C)-(D\times E\times F)=22. Divide this by 998244353 and print the remainder, which is 22.

Sample Input 2

1 1 1000000000 0 0 0

Sample Output 2

1755647

Since A\times B\times C=1000000000 and D\times E\times F=0,
we have (A\times B\times C)-(D\times E\times F)=1000000000. Divide this by 998244353 and print the remainder, which is 1755647.

Sample Input 3

1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000

Sample Output 3

0

We have (A\times B\times C)-(D\times E\times F)=0. Divide this by 998244353 and print the remainder, which is 0.

Problem Statement

We have an empty box.
Takahashi can cast the following two spells any number of times in any order.

• Spell A: puts one new ball into the box.
• Spell B: doubles the number of balls in the box.

Tell us a way to have exactly N balls in the box with at most \mathbf{120} casts of spells.
It can be proved that there always exists such a way under the Constraints given.

There is no way other than spells to alter the number of balls in the box.

Constraints

• 1 \leq N \leq 10^{18}
• All values in input are integers.

Sample Input 1

5

Sample Output 1

AABA

This changes the number of balls as follows: 0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5.
There are also other acceptable outputs, such as AAAAA.

Sample Input 2

14

Sample Output 2

BBABBAAAB

This changes the number of balls as follows: 0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14.
It is not required to minimize the length of S.

Problem Statement

You are given two sequences: A=(A_1,A_2, \ldots ,A_N) consisting of N positive integers, and B=(B_1, \ldots ,B_M) consisting of M positive integers.

Find the minimum difference of an element of A and an element of B, that is, \displaystyle \min_{ 1\leq i\leq N}\displaystyle\min_{1\leq j\leq M} \lvert A_i-B_j\rvert.

Constraints

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

Sample Input 1

2 2
1 6
4 9

Sample Output 1

2

Here is the difference for each of the four pair of an element of A and an element of B: \lvert 1-4\rvert=3, \lvert 1-9\rvert=8, \lvert 6-4\rvert=2, and \lvert 6-9\rvert=3. We should print the minimum of these values, or 2.

Sample Input 2

1 1
10
10

Sample Output 2

0

Sample Input 3

6 8
82 76 82 82 71 70
17 39 67 2 45 35 22 24

Sample Output 3

3

Problem Statement

Takahashi is trying to catch many Snuke.

There are five pits at coordinates 0, 1, 2, 3, and 4 on a number line, connected to Snuke's nest.

Now, N Snuke will appear from the pits. It is known that the i-th Snuke will appear from the pit at coordinate X_i at time T_i, and its size is A_i.

Takahashi is at coordinate 0 at time 0 and can move on the line at a speed of at most 1.
He can catch a Snuke appearing from a pit if and only if he is at the coordinate of that pit exactly when it appears.
The time it takes to catch a Snuke is negligible.

Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.

Constraints

• 1 \leq N \leq 10^5
• 0 < T_1 < T_2 < \ldots < T_N \leq 10^5
• 0 \leq X_i \leq 4
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
1 0 100
3 3 10
5 4 1

Sample Output 1

101

The optimal strategy is as follows.

• Wait at coordinate 0 to catch the first Snuke at time 1.
• Go to coordinate 4 to catch the third Snuke at time 5.

It is impossible to catch both the first and second Snuke, so this is the best he can.

Sample Input 2

3
1 4 1
2 4 1
3 4 1

Sample Output 2

0

Takahashi cannot catch any Snuke.

Sample Input 3

10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016

Sample Output 3

2978279323