Problem Statement

Given is an integer N. Determine whether there is a pair of positive integers (A, B) such that 3^A + 5^B = N, and find one such pair if it exists.

Constraints

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

Sample Input 1

106

Sample Output 1

4 2

We have 3^4 + 5^2 = 81 + 25 = 106, so (A, B) = (4, 2) satisfies the condition.

Sample Input 2

1024

Sample Output 2

-1

Sample Input 3

10460353208

Sample Output 3

21 1

Problem Statement

Given is a simple undirected graph with N vertices and M edges. The i-th edge connects Vertex c_i and Vertex d_i. Initially, Vertex i has the value a_i written on it. You want to change the values on Vertex 1, \ldots, Vertex N to b_1, \cdots, b_N, respectively, by doing the operation below zero or more times.

• Choose an edge, and let Vertex x and Vertex y be the vertices connected by that edge. Choose one of the following and do it:
  • Decrease the value a_x by 1, and increase the value a_y by 1.
  • Increase the value a_x by 1, and decrease the value a_y by 1.

Determine whether it is possible to achieve the objective by properly doing the operation.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• -10^9 \leq a_i,b_i \leq 10^9
• 1 \leq c_i,d_i \leq N
• The given graph is simple, that is, has no self-loops and no multi-edges.
• All values in input are integers.

Sample Input 1

3 2
1 2 3
2 2 2
1 2
2 3

Sample Output 1

Yes

You can achieve the objective by, for example, doing the operation as follows:

• In the first operation, choose the edge connecting Vertex 1 and 2. Then, increase a_1 by 1 and decrease a_2 by 1.
• In the second operation, choose the edge connecting Vertex 2 and 3. Then, increase a_2 by 1 and decrease a_3 by 1.

This sequence of operations makes a_1=2, a_2=2, and a_3=2.

Sample Input 2

1 0
5
5

Sample Output 2

Yes

The objective may be achieved already in the beginning.

Sample Input 3

2 1
1 1
2 1
1 2

Sample Output 3

No

There is no way to do the operation to achieve the objective.

Sample Input 4

17 9
-905371741 -999219903 969314057 -989982132 -87720225 -175700172 -993990465 929461728 895449935 -999016241 782467448 -906404298 578539175 9684413 -619191091 -952046546 125053320
-440503430 -997661446 -912471383 -995879434 932992245 -928388880 -616761933 929461728 210953513 -994677396 648190629 -530944122 578539175 9684413 595786809 -952046546 125053320
2 10
6 12
9 11
11 5
7 6
3 15
3 1
1 9
10 4

Sample Output 4

Yes

Problem Statement

Two segments [L_1:R_1] and [L_2:R_2] are said to intersect when L_1 \leq R_2 and L_2 \leq R_1 holds.

Consider the following problem P:

Input: N segments [L_1: R_1], \cdots, [L_N:R_N]
       L_1, L_2, \cdots, L_N, R_1, R_2, \cdots, R_N are pairwise distinct.
Output: the maximum number of segments that can be chosen so that no two of them intersect.

Takahashi has implemented a program that works as follows:

Sort the given segments in the increasing order of R_i and let the result be [L_{p_1}:R_{p_1}], [L_{p_2}:R_{p_2}], \cdots , [L_{p_N}:R_{p_N}].
For each i = 1, 2, \cdots , N, do the following:
  Choose [L_{p_i}:R_{p_i}] if it intersects with none of the segments chosen so far.
Print the number of chosen segments.

Aoki, on the other hand, has implemented a program that works as follows:

Sort the given segments in the increasing order of L_i and let the result be [L_{p_1}:R_{p_1}], [L_{p_2}:R_{p_2}], \cdots , [L_{p_N}:R_{p_N}].
For each i = 1, 2, \cdots , N, do the following:
  Choose [L_{p_i}:R_{p_i}] if it intersects with none of the segments chosen so far.
Print the number of chosen segments.

Given are integers N and M. Construct an input for the problem P, consisting of N segments, such that the following holds:

$$ (\text{The value printed by Takahashi's program}) - (\text{The value printed by Aoki's program}) = M $$

Constraints

• All values in input are integers.
• 1 \leq N \leq 2 \times 10^5
• -N \leq M \leq N

Sample Input 1

5 1

Sample Output 1

1 10
8 12
13 20
11 14
2 4

Let us call the five segments Segment 1, Segment 2, \cdots, Segment 5.

Takahashi's program will work as follows:

Rearrange the segments into the order Segment 5, Segment 1, Segment 2, Segment 4, Segment 3.
Choose Segment 5.
Skip Segment 1 (because it intersects with Segment 5).
Choose Segment 2.
Skip Segment 4 (because it intersects with Segment 2).
Choose Segment 3.

Thus, Takahashi's program will print 3.

Aoki's program will work as follows:

Rearrange the segments into the order Segment 1, Segment 5, Segment 2, Segment 4, Segment 3.
Choose Segment 1.
Skip Segment 5 (because it intersects with Segment 1).
Skip Segment 2 (because it intersects with Segment 1).
Choose Segment 4.
Skip Segment 3 (because it intersects with Segment 4).

Thus, Aoki's program will print 2.

Here, we have 3 - 2 = 1 \left(= M \right), and thus these five segments satisfy the condition.

Sample Input 2

10 -10

Sample Output 2

-1

Problem Statement

Given are integer sequence of length N, A = (A_1, A_2, \cdots, A_N), and an integer K.

For each X such that 1 \le X \le K, find the following value:

\left(\displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X\right) \bmod 998244353

Constraints

• All values in input are integers.
• 2 \le N \le 2 \times 10^5
• 1 \le K \le 300
• 1 \le A_i \le 10^8

Sample Input 1

3 3
1 2 3

Sample Output 1

12
50
216

In the 1-st line, we should print (1+2)^1 + (1+3)^1 + (2+3)^1 = 3 + 4 + 5 = 12.

In the 2-nd line, we should print (1+2)^2 + (1+3)^2 + (2+3)^2 = 9 + 16 + 25 = 50.

In the 3-rd line, we should print (1+2)^3 + (1+3)^3 + (2+3)^3 = 27 + 64 + 125 = 216.

Sample Input 2

10 10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

90
180
360
720
1440
2880
5760
11520
23040
46080

Sample Input 3

2 5
1234 5678

Sample Output 3

6912
47775744
805306038
64822328
838460992

Be sure to print the sum modulo 998244353.

Problem Statement

You run a shop employing N employees. Each employee comes to work in a fixed cycle. More specifically, starting today, the i-th employee repeats the following: working for A_i consecutive days and then taking A_i consecutive days off.

Every day starting today, you will come to work and give a medal to an employee of your choice who comes to work that day. (If no employee comes to work, you will do nothing that day.)

At least how many days does it takes to give every employee K or more medals?

Constraints

• All values in input are integers.
• 1 \le N \le 18
• 1 \le K \le 10^5
• 1 \le A_i \le 10^5

Sample Input 1

3 3
1 2 3

Sample Output 1

10

For example, you can choose to give them medals as follows:

• Give a medal to the 1-st employee on the 1-st, 5-th, and 9-th days.
• Give a medal to the 2-nd employee on the 2-nd, 6-th, and 10-th days.
• Give a medal to the 3-rd employee on the 3-rd, 7-th, and 8-th days.

Since no employee comes to work on the 4-th day, this is one of the ways to achieve the objective in the minimum number of days.

Sample Input 2

10 10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

199

Sample Input 3

2 5
1234 5678

Sample Output 3

10

Problem Statement

Takahashi is about to assemble a character figure, consisting of N parts called Part 1, Part 2, ..., Part N and N-1 connecting components. Parts are distinguishable, but connecting components are not.

Part i has d_i holes, called Hole 1, Hole 2, ..., Hole d_i, into which a connecting component can be inserted. These holes in the parts are distinguishable. Each connecting component will be inserted into two holes in different parts, connecting these two parts. It is impossible to insert multiple connecting components into a hole.

The character figure is said to be complete when it has the following properties:

• All of the N-1 components are used to connect parts.
• Consider a graph with N vertices corresponding to the parts and N-1 undirected edges corresponding to the pairs of vertices connected by a connecting component. Then, this graph is connected.

Two ways A and B to make the figure complete are considered the same when the following is satisfied: for every pair of holes, A uses a connecting component to connect these holes if and only if B uses one to connect them.

Find the number of ways to make the figure complete. Since the answer can be enormous, find the count modulo 998244353.

Constraints

• All values in input are integers.
• 2 \leq N \leq 2 \times 10^5
• 1 \leq d_i < 998244353

Sample Input 1

3
1 1 3

Sample Output 1

6

One way to make the figure complete is to connect Hole 1 in Part 1 and Hole 3 in Part 3 and then connect Hole 1 in Part 2 and Hole 1 in Part 3.

Sample Input 2

3
1 1 1

Sample Output 2

0

Sample Input 3

6
7 3 5 10 6 4

Sample Output 3

389183858

Sample Input 4

9
425656 453453 4320 1231 9582 54336 31435436 14342 423543

Sample Output 4

667877982