Problem Statement

There is a queue of snakes. Initially, the queue is empty.

You are given Q queries, which should be processed in the order they are given. There are three types of queries:

• Type 1: Given in the form 1 l. A snake of length l is added to the end of the queue. If the queue was empty before adding, the head position of the newly added snake is 0; otherwise, it is the sum of the head coordinate of the last snake in the queue and the last snake’s length.
• Type 2: Given in the form 2. The snake at the front of the queue leaves the queue. It is guaranteed that the queue is not empty at this time. Let m be the length of the snake that left, then the head coordinate of every snake remaining in the queue decreases by m.
• Type 3: Given in the form 3 k. Output the head coordinate of the snake that is k-th from the front of the queue. It is guaranteed that there are at least k snakes in the queue at this time.

Constraints

• 1 \leq Q \leq 3 \times 10^{5}
• For a query of type 1, 1 \leq l \leq 10^{9}
• For a query of type 2, it is guaranteed that the queue is not empty.
• For a query of type 3, let n be the number of snakes in the queue, then 1 \leq k \leq n.
• All input values are integers.

Sample Input 1

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

Sample Output 1

5
10

• 1st query: A snake of length 5 is added to the queue. Since the queue was empty, the head coordinate of this snake is 0.
• 2nd query: A snake of length 7 is added to the queue. Before adding, the last snake has head coordinate 0 and length 5, so the newly added snake’s head coordinate is 5.
• 3rd query: Output the head coordinate of the snake that is 2nd from the front. Currently, the head coordinates of the snakes in order are 0, 5, so output 5.
• 4th query: A snake of length 3 is added to the queue. Before adding, the last snake has head coordinate 5 and length 7, so the new snake’s head coordinate is 12.
• 5th query: A snake of length 4 is added to the queue. Before adding, the last snake has head coordinate 12 and length 3, so the new snake’s head coordinate is 15.
• 6th query: The snake at the front leaves the queue. The length of the snake that left is 5, so the head coordinate of each remaining snake decreases by 5. The remaining snake’s head coordinate becomes 0, 7, 10.
• 7th query: Output the head coordinate of the snake that is 3rd from the front. Currently, the head coordinates of the snakes in order are 0, 7, 10, so output 10.

Sample Input 2

3
1 1
2
1 3

Sample Output 2

It is possible that there are no queries of type 3.

Sample Input 3

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

Sample Output 3

20
5

Problem Statement

This problem is a simplified version of Problem F.

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

When splitting A at one position into two non-empty (contiguous) subarrays, find the maximum possible sum of the counts of distinct integers in those subarrays.

More formally, find the maximum sum of the following two values for an integer i such that 1 \leq i \leq N-1: the count of distinct integers in (A_1, A_2, \ldots, A_i), and the count of distinct integers in (A_{i+1}, A_{i+2}, \ldots, A_N).

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq A_i \leq N (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

5

• For i=1, (3) contains 1 distinct integer, and (1,4,1,5) contains 3 distinct integers, for a total of 4.
• For i=2, (3,1) contains 2 distinct integers, and (4,1,5) contains 3 distinct integers, for a total of 5.
• For i=3, (3,1,4) contains 3 distinct integers, and (1,5) contains 2 distinct integers, for a total of 5.
• For i=4, (3,1,4,1) contains 3 distinct integers, and (5) contains 1 distinct integer, for a total of 4.

Therefore, the maximum sum is 5 for i=2,3.

Sample Input 2

10
2 5 6 5 2 1 7 9 7 2

Sample Output 2

8

Problem Statement

Takahashi is playing with toy trains, connecting and disconnecting them.
There are N toy train cars, with car numbers: Car 1, Car 2, \ldots, Car N.
Initially, all cars are separated.

You will be given Q queries. Process them in the order they are given. There are three kinds of queries, as follows.

• 1 x y: Connect the front of Car y to the rear of Car x.
  It is guaranteed that:

  • x \neq y
  • just before this query, no train is connected to the rear of Car x;
  • just before this query, no train is connected to the front of Car y;
  • just before this query, Car x and Car y belong to different connected components.

• 2 x y: Disconnect the front of Car y from the rear of Car x.
  It is guaranteed that:

  • x \neq y;
  • just before this query, the front of Car y is directly connected to the rear of Car x.

• 3 x: Print the car numbers of the cars belonging to the connected component containing Car x, from front to back.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq x \leq N
• 1 \leq y \leq N
• All values in input are integers.
• All queries satisfy the conditions in the Problem Statement.
• The queries of the format 3 x ask to print at most 10^6 car numbers in total.

Sample Input 1

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

Sample Output 1

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

The figure below shows the cars when the first 5 queries are processed.
For example, Car 2 belongs to the same connected component as Cars 3, 5, 6, 7, which is different from the connected component containing Cars 1, 4.

The figure below shows the cars when the first 11 queries are processed.

Problem Statement

There are N rectangular cuboids in a three-dimensional space.

These cuboids do not overlap. Formally, for any two different cuboids among them, their intersection has a volume of 0.

The diagonal of the i-th cuboid is a segment that connects two points (X_{i,1},Y_{i,1},Z_{i,1}) and (X_{i,2},Y_{i,2},Z_{i,2}), and its edges are all parallel to one of the coordinate axes.

For each cuboid, find the number of other cuboids that share a face with it.
Formally, for each i, find the number of j with 1\leq j \leq N and j\neq i such that the intersection of the surfaces of the i-th and j-th cuboids has a positive area.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq X_{i,1} < X_{i,2} \leq 100
• 0 \leq Y_{i,1} < Y_{i,2} \leq 100
• 0 \leq Z_{i,1} < Z_{i,2} \leq 100
• Cuboids do not have an intersection with a positive volume.
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
1
0
0

The 1-st and 2-nd cuboids share a rectangle whose diagonal is the segment connecting two points (0,0,1) and (1,1,1).
The 1-st and 3-rd cuboids share a point (1,1,1), but do not share a surface.

Sample Input 2

3
0 0 10 10 10 20
3 4 1 15 6 10
0 9 6 1 20 10

Sample Output 2

2
1
1

Sample Input 3

8
0 0 0 1 1 1
0 0 1 1 1 2
0 1 0 1 2 1
0 1 1 1 2 2
1 0 0 2 1 1
1 0 1 2 1 2
1 1 0 2 2 1
1 1 1 2 2 2

Sample Output 3

3
3
3
3
3
3
3
3

Problem Statement

Takahashi and Aoki will work part-time for the next N days.
Takahashi's shift schedule is given by the string S, where the i-th character of S is # if he works on the i-th day, and . if he is absent on the i-th day.
Based on this, Aoki created his shift schedule as follows.

• First, take a positive divisor M of N that is not equal to N.
• Next, decide the attendance for the first M days.
• Finally, for i = 1, 2, \ldots, N - M in this order, decide the attendance for the (M + i)-th day so that it matches the attendance for the i-th day.

Note that different values of M may lead to the same final shift schedule.

Find the number of possible shift schedules for Aoki such that at least one of Takahashi and Aoki works on each of the N days, modulo 998244353.

Constraints

• N is an integer between 2 and 10^5, inclusive.
• S is a string of length N consisting of # and ..

Sample Input 1

6
##.#.#

Sample Output 1

3

Takahashi works on days 1, 2, 4, and 6.
Let T be the string representing Aoki's shift schedule, where the i-th character of T is # if he works on the i-th day, and . if he is absent on the i-th day.
There are three possible strings for T: ######, #.#.#., and .##.##.

The first shift schedule can be realized by choosing M = 1 or 2 or 3, the second by choosing M = 2, and the third by choosing M = 3.

Sample Input 2

7
...####

Sample Output 2

1

Sample Input 3

12
####.####.##

Sample Output 3

19