Problem Statement

You are given a sequence a = (a_1, \dots, a_N) of length N consisting of integers between 1 and N.

Find the number of pairs of integers i, j that satisfy all of the following conditions:

• 1 \leq i \lt j \leq N
• \min(a_i, a_j) = i
• \max(a_i, a_j) = j

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq a_i \leq N \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

4
1 3 2 4

Sample Output 1

2

(i, j) = (1, 4), (2, 3) satisfy the conditions.

Sample Input 2

10
5 8 2 2 1 6 7 2 9 10

Sample Output 2

8

Problem Statement

You are given positive integers N and Q, and a string S of length N consisting of lowercase English letters.

Process Q queries. Each query is of one of the following two types.

• 1 x: Perform the following x times in a row: delete the last character of S and append it to the beginning.
• 2 x: Print the x-th character of S.

Constraints

• 2 \le N \le 5 \times 10^5
• 1 \le Q \le 5 \times 10^5
• 1 \le x \le N
• |S|=N
• S consists of lowercase English letters.
• At least one query in the format 2 x.
• N, Q, x are all integers.

Sample Input 1

3 3
abc
2 2
1 1
2 2

Sample Output 1

b
a

In the 1-st query, S is abc, so the 2-nd character b should be printed. In the 2-nd query, S is changed from abc to cab. In the 3-rd query, S is cab, so the 2-nd character a should be printed.

Sample Input 2

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5

Sample Output 2

c
u
c
u

Problem Statement

We have an empty sequence A.
Given Q queries, process them in order.
Each query is of one of the following three types.

• 1 x : Insert x to A.

• 2 x k : Among the elements of A that are less than or equal to x, print the k-th largest value. (k is no more than \bf{5})
  If there are less than k elements of A that are less than or equal to x, then print -1.

• 3 x k : Among the elements of A that are greater than or equal to x, print the k-th smallest value. (k is no more than \bf{5})
  If there are less than k elements of A that are greater than or equal to x, then print -1.

Constraints

• 1\leq Q \leq 2\times 10^5
• 1\leq x\leq 10^{18}
• 1\leq k\leq 5
• All values in input are integers.

Sample Input 1

11
1 20
1 10
1 30
1 20
3 15 1
3 15 2
3 15 3
3 15 4
2 100 5
1 1
2 100 5

Sample Output 1

20
20
30
-1
-1
1

After \text{query}_{1,2,3,4} have been processed, we have A=(20,10,30,20).

For \text{query}_{5,6,7}, the elements of A greater than or equal to 15 are (20,30,20).
The 1-st smallest value of them is 20; the 2-nd is 20; the 3-rd is 30.

Problem Statement

Takahashi will embark on an adventure.

During the adventure, N events will occur. The i-th event (1\leq i\leq N) is represented by a pair of integers (t _ i,x _ i) (1\leq t _ i\leq 2,1\leq x _ i\leq N) and is as follows:

• If t _ i=1, he finds one potion of type x _ i. He can choose to pick it up or discard it.
• If t _ i=2, he encounters one monster of type x _ i. If he has a potion of type x _ i, he can use one to defeat the monster. If he does not defeat it, he will be defeated.

Determine whether he can defeat all the monsters without being defeated.

If he cannot defeat all the monsters, print -1.

Otherwise, let K be the maximum number of potions he has at some point during the adventure. Let K _ {\min} be the minimum value of K across all strategies where he will not be defeated. Print the value of K _ {\min} and the actions of Takahashi that achieve K _ {\min}.

Constraints

• 1\leq N\leq2\times10^5
• 1\leq t _ i\leq2\ (1\leq i\leq N)
• 1\leq x _ i\leq N\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

13
1 2
1 3
1 1
1 3
1 2
2 3
1 3
1 3
2 3
1 3
2 2
2 3
2 1

Sample Output 1

3
1 1 1 0 0 1 0 1

The sample output corresponds to the following actions:

• Find potions of types 2,3,1 in this order. Pick up all of them.
• Find potions of types 3,2 in this order. Do not pick up any of them.
• Encounter a type-3 monster. Use one type-3 potion to defeat it.
• Find a type-3 potion. Pick it up.
• Find a type-3 potion. Do not pick it up.
• Encounter a type-3 monster. Use one type-3 potion to defeat it.
• Find a type-3 potion. Pick it up.
• Encounter a type-2 monster. Use one type-2 potion to defeat it.
• Encounter a type-3 monster. Use one type-3 potion to defeat it.
• Encounter a type-1 monster. Use one type-1 potion to defeat it.

In this sequence of actions, the value of K is 3.

There is no way to avoid defeat with K\leq 2, so the sought value of K _ {\min} is 3. There are multiple sequences of actions that satisfy K=3 and allow him to avoid defeat; you may print any of them.

Sample Input 2

4
2 3
1 4
2 1
1 2

Sample Output 2

-1

He will inevitably be defeated by the first monster he encounters.

Sample Input 3

30
1 25
1 2
1 10
1 18
2 18
1 11
2 11
1 21
1 6
2 2
2 10
1 11
1 24
1 11
1 3
1 2
1 18
2 25
1 8
1 10
1 11
2 18
2 10
1 10
2 2
1 24
1 10
2 10
1 25
2 6

Sample Output 3

4
1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0

Problem Statement

There are N rooms numbered 1, 2, \ldots, N, each with one person living in it, and M corridors connecting two different rooms. The i-th corridor connects room U_i and room V_i with a length of W_i.

One day (we call this day 0), the K people living in rooms A_1, A_2, \ldots, A_K got (newly) infected with a virus. Furthermore, on the i-th of the following D days (1\leq i\leq D), the infection spread as follows.

People who were infected at the end of the night of day (i-1) remained infected at the end of the night of day i.
For those who were not infected, they were newly infected if and only if they were living in a room within a distance of X_i from at least one room where an infected person was living at the end of the night of day (i-1). Here, the distance between rooms P and Q is defined as the minimum possible sum of the lengths of the corridors when moving from room P to room Q using only corridors. If it is impossible to move from room P to room Q using only corridors, the distance is set to 10^{100}.

For each i (1\leq i\leq N), print the day on which the person living in room i was newly infected. If they were not infected by the end of the night of day D, print -1.

Constraints

• 1 \leq N\leq 3\times 10^5
• 0 \leq M\leq 3\times 10^5
• 1 \leq U_i < V_i\leq N
• All (U_i,V_i) are different.
• 1\leq W_i\leq 10^9
• 1 \leq K\leq N
• 1\leq A_1<A_2<\cdots<A_K\leq N
• 1 \leq D\leq 3\times 10^5
• 1\leq X_i\leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

0
1
1
2

The infection spreads as follows.

• On the night of day 0, the person living in room 1 gets infected.
• The distances between room 1 and rooms 2,3,4 are 2,3,5, respectively. Thus, since X_1=3, the people living in rooms 2 and 3 are newly infected on the night of day 1.
• The distance between rooms 3 and 4 is 2. Thus, since X_2=3, the person living in room 4 also gets infected on the night of day 2.

Therefore, the people living in rooms 1,2,3,4 were newly infected on days 0,1,1,2, respectively, so print 0,1,1,2 in this order on separate lines.

Sample Input 2

7 7
1 2 2
2 3 3
3 4 1
4 5 1
5 6 3
3 7 1
4 7 1
2
1 6
2
2 3

Sample Output 2

0
1
2
-1
2
0
-1

Sample Input 3

5 1
1 2 5
2
1 3
3
3 7 5

Sample Output 3

0
2
0
-1
-1

Note that it is not always possible to move between any two rooms using only corridors.