Problem Statement

You are given integers N and K. Is it possible to express N as the sum of exactly K numbers of the form 3^m (m is a non-negative integer)? In other words, is there a sequence of non-negative integers (m_1, m_2,\ldots, m_K) such that:

N= 3^{m_1}+3^{m_2}+...+3^{m_K}?

You are given T test cases. Answer each of them.

Constraints

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

Sample Input 1

4
5 3
17 2
163 79
1000000000000000000 1000000000000000000

Sample Output 1

Yes
No
Yes
Yes

For the first test case, we have 5=3^1+3^0+3^0, so the condition in question is satisfied.

For the second test case, there is no sequence of non-negative integers (m_1, m_2) such that 17=3^{m_1}+3^{m_2}, so the condition in question is not satisfied.

Problem Statement

There is a simple connected undirected graph with N vertices numbered from 1 to N. This graph has M edges, and the i-th edge connects two vertices a_i and b_i.

Each vertex has a color, either white or black, and the initial state is given by c_i. c_i is either 0 or 1, where c_i=0 means that vertex i is initially white, and c_i=1 means that vertex i is initially black.

On this graph, you can choose any vertex as your starting point and repeat the following operation as many times as you like.

• Move to a vertex of a different color connected by an edge from the current vertex. Immediately after moving, reverse the color of the vertex you moved from (change to black if it was white, and vice versa).

Is it possible to return to the starting point after performing the operation at least once?

Constraints

• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq \mathrm{min} \lbrace 2 \times 10^5,N(N-1)/2 \rbrace
• 1 \leq a_i, b_i \leq N (1 \leq i \leq M)
• c_i=0 or c_i=1 (1 \leq i \leq N)
• The given graph is simple and connected.
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes

For example, consider starting from vertex 1. In the first operation, move to vertex 2 and change the color of the vertex 1 from white to black. This change in the graph is shown in the figure below (the vertex circled is the current vertex).

Then, if you move to vertices 3, 4, and 2 in order, the colors of vertices 1,2,3,4 will then be black, white, black, and white, respectively. Therefore, you can move to vertex 1 in the next operation, returning to the starting point.

Sample Input 2

5 6
1 2
2 3
3 4
4 5
1 4
2 5
0 1 0 1 0

Sample Output 2

No

In this graph, no matter which vertex you choose as the starting point, you cannot return to the starting point by making moves that satisfy the conditions.

Problem Statement

There are N cards, each with a number written on both sides. On the i-th card, the number A_i is written in red on one side, and the number B_i is written in blue on the other side. Initially, all cards are placed with the red number side facing up. Alice and Bob play a game in which they repeat the following steps.

• First, Alice chooses one of the remaining cards and flips it over. Next, Bob removes one of the remaining cards. Then, Bob scores points equal to the number written on the face-up side of the removed card.

The game ends when there are no cards left.

Alice tries to minimize Bob's score at the end of the game, and Bob tries to maximize it. What is Bob's score at the end of the game when both players take optimal steps?

Constraints

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

Sample Input 1

3
6 4
2 1
5 3

Sample Output 1

12

In the initial state, the numbers written on the face-up sides are 6,2,5. One possible progression from here is as follows.

1. Alice flips the first card. Then, the numbers written on the face-up sides are 4,2,5. Bob removes the third card and scores 5 points.
2. Alice flips the second card. Then, the numbers written on the face-up sides are 4,1. Bob removes the second card and scores 1 point.
3. Alice flips the first card, the final one remaining. Then, the number written on the face-up side is 6. Bob removes it and scores 6 points.

In this case, Bob's final score is 12 points. In fact, this progression is an example of optimal sequences of moves for both players; the answer is 12.

Sample Input 2

5
166971716 552987438
219878198 619875818
918378176 518975015
610749017 285601372
701849287 307601390

Sample Output 2

3078692091

Problem Statement

Consider the following problem for a string s of length 2N formed by N + and N -, and let p(s) denote the answer.

There are 2N balls lined up at positions x=1,2,3,\ldots , 2N on a number line, of which N have a charge of +1 and the remaining N have a charge of -1. The arrangement of the charges of the balls is represented by s. If the i-th character of s is +, a ball with a charge of +1 is placed at x=i; if it is -, a ball with a charge of -1 is placed at x=i.

Each ball starts motion simultaneously according to the following rules. Here, we call the direction where smaller numbers are located on the number line "left", and the direction where larger numbers are located "right".

• For each ball, define F at each moment by the following formula:
  F=\lbrace (the sum of the charges of the balls strictly to the left of itself) - (the sum of the charges of the balls strictly to the right of itself) \rbrace \times (the charge of itself).
• At each moment, each ball moves to the right if F is positive, and to the left if F is negative, at a speed of 1 per second.
• If a ball with a charge of +1 and a ball with a charge of -1 exist at the same coordinate simultaneously, they cancel out each other and disappear.

Then, what is the sum of the distances moved by the balls after they start motion and before they disappear (the distance moved by a ball is the absolute difference between the coordinates where it starts and where it disappears)?

You are given a string T of length 2N consisting of +, -, and ?. Find the sum of p(s) over all strings s formed by N + and N - that can be obtained by replacing each ? in T with + or -, modulo 998244353.

Under the given constraints and the rules of motion, it can be shown that all balls disappear in finite time, that the value of F for each ball does not become 0 until that ball disappears, that there is no moment when three or more balls are at the same coordinate simultaneously, and that p(s) is an integer.

Constraints

• 1\leq N\leq 3000
• N is an integer.
• |T|=2N
• Each character of T is either +, -, or ?, and there are at most N + and at most N -.

Sample Input 1

2
+??-

Sample Output 1

6

The strings s that can be obtained from T are ++-- and +-+-.

For ++--, the sum of the charges of the balls to the left and right of each ball, and the value of F at the start of the motion are as follows:

Thus, the balls at x=1,2 start moving to the right, and the balls at x=3,4 start moving to the left. Then, each ball continues to move in the same direction without changing its direction of motion, and the balls that started at x=2,3 disappear at x=2.5 after 0.5 seconds, and the balls that started at x=1,4 disappear at x=2.5 after 1.5 seconds. During these times, the balls that started at x=2,3 move a distance of 0.5 each, and the balls that started at x=1,4 move a distance of 1.5 each, so p( ++-- )=4.

Similarly, it can be seen that p( +-+- )=2, so the sought sum of p(s) is 6.

Sample Input 2

17
??????????????????????????????????

Sample Output 2

285212526

Be sure to print the sum of p(s) modulo 998244353.

Problem Statement

There is a sequence of N terms, and Q queries will be given on this sequence. The i-th query is for the interval [L_i, R_i] (the interval [a,b] is a set of integers between a and b, inclusive).

You will answer this problem using a binary tree that satisfies the following conditions. Here, i,j,k represent integers.

• Each node has an interval.
• The root node has the interval [1, N].
• The node with the interval [i, i] is a leaf. Also, the interval of a leaf can be represented as [i,i].
• Each non-leaf node has exactly two children. Also, if the interval of a non-leaf node is [i,j], the intervals of the children of this node are [i,k] and [k+1,j] (i\leq k<j).

In this binary tree, when a query for the interval [L,R] is given, a search is performed recursively according to the following rules.

1. Initially, the root is investigated.
2. When a node is investigated, if the interval of this node is included in [L, R], its descendants are not investigated.
3. When a node is investigated, if the interval of this node have no intersection with [L,R], its descendants are not investigated.
4. When a node is investigated, if neither 2. nor 3. applies, the two child nodes are investigated. (It can be shown that either 2. or 3. always applies to a leaf node.)

When answering Q queries, let d be the maximum depth (distance from the root) of the investigated nodes, and c be the total number of times nodes of depth d are investigated. Here, if multiple nodes of depth d are investigated in a single query, or if the same node is investigated in multiple queries, all those investigations count separately.

You want to design the binary tree to minimize d, and then to minimize c while minimizing d. What are the values of d and c then?

Constraints

• 2\leq N \leq 4000
• 1\leq Q \leq 10^5
• 1\leq L_i \leq R_i \leq N (1\leq i \leq Q)
• All input values are integers.

Sample Input 1

6 4
2 3
3 4
2 4
3 3

Sample Output 1

3 4

We have an interval [1,6], and queries for the intervals [2,3],[3,4],[2,4],[3,3]. Here, if you use the binary tree shown in the figure below,

• for the first query, nodes 1,2,3,4,5 are investigated, and the maximum depth among these is 2 for nodes 4,5;
• for the second query, nodes 1,2,3,4,5,6,7,8,9 are investigated, and the maximum depth among these is 3 for nodes 8,9;
• for the third query, nodes 1,2,3,4,5,6,7 are investigated, and the maximum depth among these is 2 for nodes 4,5,6,7;
• for the fourth query, nodes 1,2,3,4,5,8,9 are investigated, and the maximum depth among these is 3 for nodes 8,9.

Therefore, in this case, d=3, and nodes of depth 3 were investigated four times ー nodes 8,9 in the second query and nodes 8,9 in the fourth query ー so c=4. In fact, this is an optimal method.

(In the figure, the upper row shows the node number, and the lower row shows the interval of each node.)

Sample Input 2

12 6
1 10
2 7
3 6
4 9
5 8
11 12

Sample Output 2

4 4

Problem Statement

You are given a rooted tree with N vertices numbered from 1 to N, rooted at vertex 1. The parent of vertex i is vertex p_i (2\leq i\leq N).

Alice and Bob play a game using this tree as follows.

• Alice goes first, and Bob goes second. They take turns placing a stone, with a white side and a black side, on a vertex of the tree. Alice places the stone with the white side up, and Bob places the stone with the black side up.
• In each turn, a stone can only be placed on a vertex that does not have a stone on itself while all its descendants already have stones on them.
• When placing a stone on a vertex, all the stones on the descendants of that vertex are flipped over (the placed stone itself is not flipped).

The game ends when all vertices have stones. Alice's score is the number of stones with the white side up at this point.

Alice tries to maximize her score, and Bob tries to minimize Alice's score. If both play optimally, what will be Alice's score?

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq p_i < i (2\leq i \leq N)
• All input values are integers.
• The given graph is a tree.

Sample Input 1

4
1 1 2

Sample Output 1

2

In the given tree, the only vertices where a stone can be placed initially are 3 and 4. One possible progression from here is as follows.

• Alice places a stone with the white side up on vertex 4. After this operation, all descendants of vertex 2 have stones, so it is now possible to place a stone on vertex 2.
• Bob places a stone with the black side up on vertex 2 and flips the stone on vertex 4 to have the black side up.
• Alice places a stone with the white side up on vertex 3.
• Bob places a stone with the black side up on vertex 1 and flips all the stones on vertices 2, 3, and 4.

In this case, at the end of the game, the stones on vertices 1, 2, 3, and 4 have black, white, black, and white sides up, respectively. In fact, this progression is an example of optimal sequences of moves for both players; the answer is 2.

Sample Input 2

7
1 1 2 4 4 4

Sample Output 2

5