Problem Statement

You are given a string S of length N and a string T of length M, both consisting of digits from 1 to 9.

You will perform the following operation for k=1,2,\ldots,M in order:

• Choose an integer i such that 1 \le i \le N. Then, replace the i-th character of S with the k-th character of T.

Find the maximum possible value of the resulting string S interpreted as an integer after performing the M operations.

Constraints

• 1 \le N,M \le 10^6
• N and M are integers.
• S is a string of length N consisting of digits from 1 through 9.
• T is a string of length M consisting of digits from 1 through 9.

Sample Input 1

3 3
191
325

Sample Output 1

593

The following sequence of operations is optimal:

• For k=1: Choose i=3. Then, S = 193.
• For k=2: Choose i=1. Then, S = 293.
• For k=3: Choose i=1. Then, S = 593.

In this case, the value of S interpreted as an integer is 593, which is the maximum.

Sample Input 2

3 9
191
998244353

Sample Output 2

993

Sample Input 3

11 13
31415926535
2718281828459

Sample Output 3

98888976555

Problem Statement

You are given two positive integers N and K. A positive integer X is called compatible with N if it satisfies the following condition:

• The bitwise XOR of X and N is equal to the remainder when X is divided by N.

Determine whether there exist at least K such integers X that are compatible with N. If they do exist, find the K-th smallest such integer.

You are given T test cases; solve each of them.

Constraints

• 1 \le T \le 2\times 10^5
• 1 \le N,K \le 10^9
• All input values are integers.

Sample Input 1

4
2 1
2 2
1 7
20250126 191

Sample Output 1

2
3
-1
20381694

Consider the case N=2.

• When X=1, X\ \mathrm{XOR}\ N = 3 and the remainder of X when divided by N is 1. Therefore, 1 is not compatible with N.
• When X=2, X\ \mathrm{XOR}\ N = 0 and the remainder of X when divided by N is 0. Therefore, 2 is compatible with N.
• When X=3, X\ \mathrm{XOR}\ N = 1 and the remainder of X when divided by N is 1. Therefore, 3 is compatible with N.

Hence, among the numbers that are compatible with 2, the smallest is 2 and the second smallest is 3. Therefore, the answer to \text{case}_1 is 2 and the answer to \text{case}_2 is 3.

Problem Statement

You are given a positive integer N between 1 and 10^9, inclusive.

Find one pair of positive integers (A, M) satisfying the following conditions. It can be proved that such a pair of integers always exists under the constraints.

• Both A and M are positive integers between 1 and 10^{18}, inclusive.
• There exists a positive integer n such that A^n - 1 is a multiple of M, and the smallest such n is N.

You are given T test cases; solve each of them.

Constraints

• 1 \le T \le 10^4
• 1 \le N \le 10^9
• All input values are integers.

Sample Input 1

4
3
16
1
55

Sample Output 1

2 7
11 68
20250126 1
33 662

Consider \text{case}_1.

For example, if we choose (A,M)=(2,7), then:

• When n=1: 2^1 - 1 = 1 is not a multiple of 7.
• When n=2: 2^2 - 1 = 3 is not a multiple of 7.
• When n=3: 2^3 - 1 = 7 is a multiple of 7.

Hence, the smallest n for which A^n - 1 is a multiple of M is 3. Therefore, (A,M)=(2,7) is a correct solution. Other valid solutions include (A,M)=(100,777).

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges, where the vertices are numbered 1 to N and the edges are numbered 1 to M. Edge i connects vertex u_i and vertex v_i in both directions.

Initially, there is a piece A on vertex S and a piece B on vertex T. Here, S and T are given as input.

You may perform the following operation any number of times in any order:

• Choose either piece A or piece B, and move it from its current vertex to an adjacent vertex via an edge. However, you cannot make a move that results in both pieces ending up on the same vertex.

Your goal is to reach the state in which piece A is on vertex T and piece B is on vertex S.

Determine whether this is possible, and if it is, find the minimum number of operations required to achieve it.

Constraints

• 2 \le N \le 2\times 10^5
• \displaystyle N-1 \le M \le \min\left(\frac{N(N-1)}{2},\,2\times 10^5\right)
• 1 \le u_i < v_i \le N
• The given graph is simple and connected.
• 1 \le S, T \le N
• S \neq T
• All input values are integers.

Sample Input 1

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

Sample Output 1

3

For example, the following sequence of operations completes the goal in three moves:

1. Move piece A to vertex 2.
   • Piece A is on vertex 2, piece B is on vertex 4.
2. Move piece B to vertex 3.
   • Piece A is on vertex 2, piece B is on vertex 3.
3. Move piece A to vertex 4.
   • Piece A is on vertex 4, piece B is on vertex 3.

It is impossible to complete the goal in fewer than three moves, so print 3.

Sample Input 2

2 1 1 2
1 2

Sample Output 2

-1

No matter how you move the pieces, you cannot achieve the goal.

Sample Input 3

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

Sample Output 3

4

Problem Statement

You are given positive integers N, X, and Y, and two length-N sequences of non-negative integers A = (A_1,A_2,\ldots,A_N) and B = (B_1,B_2,\ldots,B_N).

There are N bags, numbered from 1 to N. Initially, bag i contains A_i gold coins and B_i silver coins.

Consider the following game played by Takahashi and Aoki using these N bags. First, Takahashi takes some of these bags (possibly zero), and Aoki takes all remaining bags. Then, starting with Takahashi, the two players alternate performing the following operation.

• Choose one bag held by the player with at least one gold coin or silver coin in it, and do one of the following two actions for that bag.
  • Remove one gold coin and add silver coins; the number of silver coins to be added is X for Takahashi and Y for Aoki. This action can only be done if the chosen bag has at least one gold coin.
  • Remove one silver coin. This action can only be done if the chosen bag has at least one silver coin.
• Then, give the chosen bag to the other player.

The player who cannot perform the operation loses the game.

Find the number, modulo 998244353, of ways Takahashi can initially take bags so that he will win under optimal play by both players.

Constraints

• 1 \le N \le 2\times 10^5
• 1 \le X, Y \le 10^9
• 0 \le A_i, B_i \le 10^9
• All input values are integers.

Sample Input 1

2 1 1
1 0
1 1

Sample Output 1

2

Consider the case where Takahashi initially takes bags 1 and 2. One possible progression of the game is as follows:

1. Takahashi chooses bag 2, removes 1 gold coin, and adds 1 silver coin. Then, he gives bag 2 to Aoki.
   • Takahashi holds bag 1 with 1 gold coin. Aoki holds bag 2 with 2 silver coins.
2. Aoki chooses bag 2 and removes 1 silver coin. Then, gives bag 2 to Takahashi.
   • Takahashi holds bags 1 with 1 gold coin and bag 2 with 1 silver coin. Aoki holds none.
3. Takahashi chooses bag 1, removes 1 gold coin, and adds 1 silver coin. Then, he gives bag 1 to Aoki.
   • Takahashi holds bag 2 with 1 silver coin. Aoki holds bag 1 with 1 silver coin.
4. Aoki chooses bag 1, removes 1 silver coin. Then, he gives bag 1 to Takahashi.
   • Takahashi holds bag 1 which is empty and bag 2 with 1 silver coin. Aoki holds none.
5. Takahashi chooses bag 2 and removes 1 silver coin. Then, he gives bag 2 to Aoki.
   • Takahashi holds bag 1 which is empty. Aoki holds bag 2 which is empty.
6. Aoki cannot perform the operation, so Aoki loses and Takahashi wins.

Takahashi can win if he initially takes only bag 2, or if he takes both bags 1 and 2. Therefore, the answer is 2.

Sample Input 2

2 2 1
1 2
1 2

Sample Output 2

3

Takahashi wins if he initially takes bag 1, bag 2, or both.

Sample Input 3

5 8 3
0 0
0 0
0 0
0 0
0 0

Sample Output 3

0

No matter how Takahashi chooses the bags initially, he will lose.

Sample Input 4

7 2025 191
1323 9953
2763 3225
2624 5938
6718 2998
3741 7040
9837 1681
8817 4471

Sample Output 4

40