Problem Statement

Given N, print 2^N.

Constraints

• 0 \leq N \leq 30
• N is an integer.

Sample Input 1

3

Sample Output 1

8

We have 2^3=8.

Sample Input 2

30

Sample Output 2

1073741824

Problem Statement

Takahashi is trying to create a game inspired by baseball, but he is having difficulty writing the code.
Write a program for Takahashi that solves the following problem.

There are 4 squares called Square 0, Square 1, Square 2, and Square 3. Initially, all squares are empty.
There is also an integer P; initially, P = 0.
Given a sequence of positive integers A = (A_1, A_2, \dots, A_N), perform the following operations for i = 1, 2, \dots, N in this order:

1. Put a piece on Square 0.
2. Advance every piece on the squares A_i squares ahead. In other words, if Square x has a piece, move the piece to Square (x + A_i).
   If, however, the destination square does not exist (i.e. x + A_i is greater than or equal to 4) for a piece, remove it. Add to P the number of pieces that have been removed.

Print the value of P after all the operations have been performed.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 4
• All values in input are integers.

Sample Input 1

4
1 1 3 2

Sample Output 1

3

The operations are described below. After all the operations have been performed, P equals 3.

• The operations for i=1:
  1. Put a piece on Square 0. Now, Square 0 has a piece.
  2. Advance every piece on the squares 1 square ahead. After these moves, Square 1 has a piece.
• The operations for i=2:
  1. Put a piece on Square 0. Now, Squares 0 and 1 have a piece.
  2. Advance every piece on the squares 1 square ahead. After these moves, Squares 1 and 2 have a piece.
• The operations for i=3:
  1. Put a piece on Square 0. Now, Squares 0, 1, and 2 have a piece.
  2. Advance every piece on the squares 3 squares ahead.
     Here, for the pieces on Squares 1 and 2, the destination squares do not exist (since 1+3=4 and 2+3=5), so remove these pieces and add 2 to P. P now equals 2. After these moves, Square 3 has a piece.
• The operations for i=4:
  1. Put a piece on Square 0. Now, Squares 0 and 3 have a piece.
  2. Advance every piece on the squares 2 squares ahead.
     Here, for the piece on Square 3, the destination square does not exist (since 3+2=5), so remove this piece and add 1 to P. P now equals 3.
     After these moves, Square 2 has a piece.

Sample Input 2

3
1 1 1

Sample Output 2

0

The value of P may not be updated by the operations.

Sample Input 3

10
2 2 4 1 1 1 4 2 2 1

Sample Output 3

8

Problem Statement

You are given six integers: h_1, h_2, h_3, w_1, w_2, and w_3.
Consider writing a positive integer on each square of a 3 \times 3 grid so that all of the following conditions are satisfied:

• For i=1,2,3, the sum of numbers written in the i-th row from the top is h_i.
• For j=1,2,3, the sum of numbers written in the j-th column from the left is w_i.

For example, if (h_1, h_2, h_3) = (5, 13, 10) and (w_1, w_2, w_3) = (6, 13, 9), then all of the following three ways satisfy the conditions. (There are other ways to satisfy the conditions.)

How many ways are there to write numbers to satisfy the conditions?

Constraints

• 3 \leq h_1, h_2, h_3, w_1, w_2, w_3 \leq 30
• All values in input are integers.

Sample Input 1

3 4 6 3 3 7

Sample Output 1

1

The following is the only way to satisfy the conditions. Thus, 1 should be printed.

Sample Input 2

3 4 5 6 7 8

Sample Output 2

0

There may not be a way to satisfy the conditions.

Sample Input 3

5 13 10 6 13 9

Sample Output 3

120

Sample Input 4

20 25 30 22 29 24

Sample Output 4

30613

Problem Statement

For real numbers L and R, let us denote by [L,R) the set of real numbers greater than or equal to L and less than R. Such a set is called a right half-open interval.

You are given N right half-open intervals [L_i,R_i). Let S be their union. Represent S as a union of the minimum number of right half-open intervals.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq L_i \lt R_i \leq 2\times 10^5
• All values in input are integers.

Sample Input 1

3
10 20
20 30
40 50

Sample Output 1

10 30
40 50

The union of the three right half-open intervals [10,20),[20,30),[40,50) equals the union of two right half-open intervals [10,30),[40,50).

Sample Input 2

3
10 40
30 60
20 50

Sample Output 2

10 60

The union of the three right half-open intervals [10,40),[30,60),[20,50) equals the union of one right half-open interval [10,60).

Problem Statement

There are N people numbered 1 through N.
Takahashi has decided to choose a sequence P = (P_1, P_2, \dots, P_N) that is a permutation of integers from 1 through N, and give a candy to Person P_1, Person P_2, \dots, and Person P_N, in this order.
Since Person i dislikes Person X_i, if Takahashi gives a candy to Person X_i prior to Person i, then Person i gains frustration of C_i; otherwise, Person i's frustration is 0.
Takahashi may arbitrarily choose P. What is the minimum possible sum of their frustration?

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq X_i \leq N
• X_i \neq i
• 1 \leq C_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
2 3 2
1 10 100

Sample Output 1

10

If he lets P = (1, 3, 2), only Person 2 gains a positive amount of frustration, in which case the sum of their frustration is 10.
Since it is impossible to make the sum of frustration smaller, the answer is 10.

Sample Input 2

8
7 3 5 5 8 4 1 2
36 49 73 38 30 85 27 45

Sample Output 2

57

Problem Statement

You are given N, Q, and A=(A_1,\ldots,A_N).
Process Q queries, each of which is of one of the following two kinds:

• 1 x v: update A_x to v.
• 2 x: let B_i=\sum_{j=1}^{i}A_j, C_i=\sum_{j=1}^{i}B_j, and D_i=\sum_{j=1}^{i}C_j. Print D_x modulo 998244353.

Constraints

• 1 \leq N \leq 2\times10^5
• 1 \leq Q \leq 2\times10^5
• 0 \leq A_i \leq 10^9
• 1 \leq x \leq N
• 0 \leq v \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

15
9

When the 1-st query is given, A=(1,2,3), so B=(1,3,6), C=(1,4,10), and D=(1,5,15); thus, D_3=15.

When the 3-rd query is given, A=(1,0,3), so B=(1,1,4), C=(1,2,6), and D=(1,3,9); thus, D_3=9.

Sample Input 2

2 1
998244353 998244353
2 1

Sample Output 2

0

Problem Statement

There is a regular N-gon with side length D.

Starting from a vertex, we place black or white stones on the circumference at intervals of 1. As a result, each edge of the N-gon will have (D+1) stones on it, for a total of ND stones.

How many ways are there to place stones so that all edges have the same number of white stones on them? Find the count modulo 998244353.

Constraints

• 3 \leq N \leq 10^{12}
• 1 \leq D \leq 10^4
• All values in input are integers.

Sample Input 1

3 2

Sample Output 1

10

There are 10 ways, as follows:

Sample Input 2

299792458 3141

Sample Output 2

138897974

Find the count modulo 998244353.

Problem Statement

You are given N, Q, and A=(a_1,\ldots,a_N).
Process Q queries described below. Each query is of one of the following three kinds:

• 1 L R x: for i=L,L+1,\dots,R, update the value of a_i to \displaystyle \left\lfloor \frac{a_i}{x} \right\rfloor.
• 2 L R y: for i=L,L+1,\dots,R, update the value of a_i to y.
• 3 L R: print \displaystyle\sum_{i=L}^R a_i.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq Q \leq 10^5
• 1 \leq L \leq R \leq N
• 1 \leq a_i \leq 10^5
• 2 \leq x \leq 10^5
• 1 \leq y \leq 10^5
• All values in input are integers.

Sample Input 1

3 5
2 5 6
3 1 3
1 2 3 2
3 1 2
2 1 2 3
3 1 3

Sample Output 1

13
4
9

Initially, A = (2, 5, 6). Thus, the answer to the 1-st query is a_1 + a_2 + a_3 = 2 + 5 + 6 = 13.
When the 2-nd query has been processed, A = (2, 2, 3). Thus, the answer to the 3-rd query is a_1 + a_2 = 2 + 2 = 4.
When the 4-th query has been processed, A = (3, 3, 3). Thus, the answer to the 5-th query is a_1 + a_2 + a_3 = 3 + 3 + 3 = 9.

Sample Input 2

6 11
10 3 5 20 6 7
3 1 6
1 2 4 3
3 1 3
2 1 4 10
3 3 6
1 3 6 2
2 1 4 5
3 1 6
2 1 3 100
1 2 5 6
3 1 4

Sample Output 2

51
12
33
26
132