1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Microwavable Subsequence
Contest: 2024-2025 ICPC Asia Jakarta Regional Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 2100
Tags: data structures

You are given an array of $$$N$$$ integers: $$$[A_1, A_2, \dots, A_N]$$$.

A subsequence can be derived from an array by removing zero or more elements without changing the order of the remaining elements. For example, $$$[2, 1, 2]$$$, $$$[3, 3]$$$, $$$[1]$$$, and $$$[3, 2, 1, 3, 2]$$$ are subsequences of array $$$[3, 2, 1, 3, 2]$$$, while $$$[1, 2, 3]$$$ is not a subsequence of array $$$[3, 2, 1, 3, 2]$$$.

A subsequence is microwavable if the subsequence consists of at most two distinct values and each element differs from its adjacent elements. For example, $$$[2, 1, 2]$$$, $$$[3, 2, 3, 2]$$$, and $$$[1]$$$ are microwavable, while $$$[3, 3]$$$ and $$$[3, 2, 1, 3, 2]$$$ are not microwavable.

Denote a function $$$f(x, y)$$$ as the length of the longest microwavable subsequence of array $$$A$$$ such that each element within the subsequence is either $$$x$$$ or $$$y$$$. Find the sum of $$$f(x, y)$$$ for all $$$1 \leq x < y \leq M$$$.

Input format:
The first line consists of two integers $$$N$$$ $$$M$$$ ($$$1 \leq N, M \leq 300\,000$$$).

The second line consists of $$$N$$$ integers $$$A_i$$$ ($$$1 \leq A_i \leq M$$$).

Output format:
Output a single integer representing the sum of $$$f(x, y)$$$ for all $$$1 \leq x < y \leq M$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Note:
Explanation for the sample input/output #1

The value of $$$f(1, 2)$$$ is $$$3$$$, taken from the subsequence $$$[2, 1, 2]$$$ that can be obtained by removing $$$A_1$$$ and $$$A_4$$$. The value of $$$f(1, 3)$$$ is $$$3$$$, taken from the subsequence $$$[3, 1, 3]$$$ that can be obtained by removing $$$A_2$$$ and $$$A_5$$$. The value of $$$f(2, 3)$$$ is $$$4$$$, taken from the subsequence $$$[3, 2, 3, 2]$$$ that can be obtained by removing $$$A_3$$$. The value of $$$f(1, 4)$$$, $$$f(2, 4)$$$, and $$$f(3, 4)$$$ are all $$$1$$$.

Explanation for the sample input/output #2

The value of $$$f(1, 2)$$$ and $$$f(1, 3)$$$ are both $$$1$$$, while the value of $$$f(2, 3)$$$ is $$$0$$$.

Example input:
5 4
3 2 1 3 2

Example output:
13

Example input:
3 3
1 1 1

Example output:
2

Editorial:
Xorderable Array
Contest: 2024-2025 ICPC Asia Jakarta Regional Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 2600
Tags: bitmasks, data structures

You are given an array $$$A$$$ of $$$N$$$ integers: $$$[A_1, A_2, \dots, A_N]$$$.

The array $$$A$$$ is $$$(p, q)$$$-xorderable if it is possible to rearrange $$$A$$$ such that for each pair $$$(i, j)$$$ that satisfies $$$1 \leq i < j \leq N$$$, the following conditions must be satisfied after the rearrangement: $$$A_i \oplus p \leq A_j \oplus q$$$ and $$$A_i \oplus q \leq A_j \oplus p$$$. The operator $$$\oplus$$$ represents the bitwise xor.

You are given another array $$$X$$$ of length $$$M$$$: $$$[X_1, X_2, \dots, X_M]$$$. Calculate the number of pairs $$$(u, v)$$$ where array $$$A$$$ is $$$(X_u, X_v)$$$-xorderable for $$$1 \leq u < v \leq M$$$.

Input format:
The first line consists of two integers $$$N$$$ $$$M$$$ ($$$2 \leq N, M \leq 200\,000)$$$.

The second line consists of $$$N$$$ integers $$$A_i$$$ ($$$0 \leq A_i < 2^{30})$$$.

The third line consists of $$$M$$$ integers $$$X_u$$$ ($$$0 \leq X_u < 2^{30})$$$.

Output format:
Output a single integer representing the number of pairs $$$(u, v)$$$ where array $$$A$$$ is $$$(X_u, X_v)$$$-xorderable for $$$1 \leq u < v \leq M$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Note:
Explanation for the sample input/output #1

The array $$$A$$$ is $$$(1, 1)$$$-xorderable by rearranging the array $$$A$$$ to $$$[0, 0, 3]$$$.

Explanation for the sample input/output #2

The array $$$A$$$ is $$$(12, 10)$$$-xorderable by rearranging the array $$$A$$$ to $$$[13, 0, 7, 24, 22]$$$.

Example input:
3 4
0 3 0
1 2 1 1

Example output:
3

Example input:
5 2
0 7 13 22 24
12 10

Example output:
1

Editorial:
GCDDCG
Contest: 2024-2025 ICPC Asia Jakarta Regional Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 2900

You are playing the Greatest Common Divisor Deck-Building Card Game (GCDDCG). There are $$$N$$$ cards (numbered from $$$1$$$ to $$$N$$$). Card $$$i$$$ has the value of $$$A_i$$$, which is an integer between $$$1$$$ and $$$N$$$ (inclusive).

The game consists of $$$N$$$ rounds (numbered from $$$1$$$ to $$$N$$$). Within each round, you need to build two non-empty decks, deck $$$1$$$ and deck $$$2$$$. A card cannot be inside both decks, and it is allowed to not use all $$$N$$$ cards. In round $$$i$$$, the greatest common divisor (GCD) of the card values in each deck must equal $$$i$$$.

Your creativity point during round $$$i$$$ is the product of $$$i$$$ and the number of ways to build two valid decks. Two ways are considered different if one of the decks contains different cards.

Find the sum of creativity points across all $$$N$$$ rounds. Since the sum can be very large, calculate the sum modulo $$$998\,244\,353$$$.

Input format:
The first line consists of an integer $$$N$$$ ($$$2 \leq N \leq 200\,000)$$$.

The second line consists of $$$N$$$ integers $$$A_i$$$ ($$$1 \leq A_i \leq N$$$).

Output format:
Output a single integer representing the sum of creativity points across all $$$N$$$ rounds modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Note:
Explanation for the sample input/output #1

The creativity point during each of rounds $$$1$$$ and $$$2$$$ is $$$0$$$.

During round $$$3$$$, there are $$$12$$$ ways to build both decks. Denote $$$B$$$ and $$$C$$$ as the set of card numbers within deck $$$1$$$ and deck $$$2$$$, respectively. The $$$12$$$ ways to build both decks are:

- $$$B = \{ 1 \}, C = \{ 2 \}$$$;
- $$$B = \{ 1 \}, C = \{ 3 \}$$$;
- $$$B = \{ 1 \}, C = \{ 2, 3 \}$$$;
- $$$B = \{ 2 \}, C = \{ 1 \}$$$;
- $$$B = \{ 2 \}, C = \{ 3 \}$$$;
- $$$B = \{ 2 \}, C = \{ 1, 3 \}$$$;
- $$$B = \{ 3 \}, C = \{ 1 \}$$$;
- $$$B = \{ 3 \}, C = \{ 2 \}$$$;
- $$$B = \{ 3 \}, C = \{ 1, 2 \}$$$;
- $$$B = \{ 1, 2 \}, C = \{ 3 \}$$$;
- $$$B = \{ 2, 3 \}, C = \{ 1 \}$$$; and
- $$$B = \{ 1, 3 \}, C = \{ 2 \}$$$.

Explanation for the sample input/output #2

For rounds $$$1$$$, $$$2$$$, $$$3$$$ and $$$4$$$, there are $$$0$$$, $$$18$$$, $$$0$$$, and $$$2$$$ ways to build both decks, respectively.

Example input:
3
3 3 3

Example output:
36

Example input:
4
2 2 4 4

Example output:
44

Editorial:
Buggy DFS
Contest: 2024-2025 ICPC Asia Jakarta Regional Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
Difficulty rating: 3000
Tags: constructive algorithms

You are currently studying a graph traversal algorithm called the Depth First Search (DFS). However, due to a bug, your algorithm is slightly different from the standard DFS. The following is an algorithm for your Buggy DFS (BDFS), assuming the graph has $$$N$$$ nodes (numbered from $$$1$$$ to $$$N$$$).

You realized that the bug made the algorithm slower than standard DFS, which can be investigated by the return value of the function BDFS(). To investigate the behavior of this algorithm, you want to make some test cases by constructing an undirected simple graph such that the function BDFS() returns $$$K$$$, or determine if it is impossible to do so.

Input format:
A single line consisting of an integer $$$K$$$ ($$$1 \leq K \leq 10^9$$$).

Output format:
If it is impossible to construct an undirected simple graph such that the function BDFS() returns $$$K$$$, then output -1 -1 in a single line.

Otherwise, output the graph in the following format. The first line consists of two integers $$$N$$$ and $$$M$$$, representing the number of nodes and undirected edges in the graph, respectively. Each of the next $$$M$$$ lines consists of two integers $$$u$$$ and $$$v$$$, representing an undirected edge that connects node $$$u$$$ and node $$$v$$$. You are allowed to output the edges in any order. This graph has to satisfy the following constraints:

- $$$1 \leq N \leq 32\,768$$$
- $$$1 \leq M \leq 65\,536$$$
- $$$1 \leq u, v \leq N$$$, for all edges.
- The graph is a simple graph, i.e. there are no multi-edges nor self-loops.

Note that you are not required to minimize the number of nodes or edges. It can be proven that if constructing a graph in which the return value of BDFS() is $$$K$$$ is possible, then there exists one that satisfies all the constraints above. If there are several solutions, you can output any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Note:
Explanation for the sample input/output #1

The graph on the left describes the output of this sample. The graph on the right describes another valid solution for this sample.

Explanation for the sample input/output #3

The following graph describes the output of this sample.

Example input:
8

Example output:
3 3
1 2
1 3
2 3

Example input:
1

Example output:
-1 -1

Editorial:
Rectangle Arrangement
Contest: Codeforces Round 982 (Div. 2)
Difficulty rating: 800
Tags: geometry, implementation, math

You are coloring an infinite square grid, in which all cells are initially white. To do this, you are given $$$n$$$ stamps. Each stamp is a rectangle of width $$$w_i$$$ and height $$$h_i$$$.

You will use each stamp exactly once to color a rectangle of the same size as the stamp on the grid in black. You cannot rotate the stamp, and for each cell, the stamp must either cover it fully or not cover it at all. You can use the stamp at any position on the grid, even if some or all of the cells covered by the stamping area are already black.

What is the minimum sum of the perimeters of the connected regions of black squares you can obtain after all the stamps have been used?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$).

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$w_i$$$ and $$$h_i$$$ ($$$1 \le w_i, h_i \le 100$$$).

Output format:
For each test case, output a single integer — the minimum sum of the perimeters of the connected regions of black squares you can obtain after all the stamps have been used.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the stamps can be used as shown on the left. Each stamp is highlighted in its own color for clarity.

After all these stamps are used, there is one black region (as shown on the right), and its perimeter is $$$20$$$. It can be shown that there is no way of using the stamps that yields a lower total perimeter.

In the second test case, the second and third stamps can be used entirely inside the first one, so the minimum perimeter is equal to $$$8$$$.

Example input:
5
5
1 5
2 4
3 3
4 2
5 1
3
2 2
1 1
1 2
1
3 2
3
100 100
100 100
100 100
4
1 4
2 3
1 5
3 2

Example output:
20
8
10
400
16

Editorial:
We must minimize the perimeter, and an obvious way to attempt this is to maximize the overlap. To achieve this, we can place each stamp such that the lower left corner of each stamp is at the same position, like shown in the sample explanation.
Now, we can observe that the perimeter of this shape is determined solely by the maximum height and width of any stamp, and these values cannot be reduced further. Therefore, the answer is $$$2 \cdot \bigl( \max(a_i) + \max(b_i) \bigr)$$$.
Furthermore, it's true that any arrangement of stamps which are fully enclosed in an outer rectangular area of $$$\max(a_i)$$$ by $$$\max(b_i)$$$ will yield the same perimeter.
Fibonacciness
Contest: Codeforces Round 998 (Div. 3)
Difficulty rating: 800
Tags: brute force

There is an array of $$$5$$$ integers. Initially, you only know $$$a_1,a_2,a_4,a_5$$$. You may set $$$a_3$$$ to any positive integer, negative integer, or zero. The Fibonacciness of the array is the number of integers $$$i$$$ ($$$1 \leq i \leq 3$$$) such that $$$a_{i+2}=a_i+a_{i+1}$$$. Find the maximum Fibonacciness over all integer values of $$$a_3$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 500$$$) — the number of test cases.

The only line of each test case contains four integers $$$a_1, a_2, a_4, a_5$$$ ($$$1 \leq a_i \leq 100$$$).

Output format:
For each test case, output the maximum Fibonacciness on a new line.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can set $$$a_3$$$ to $$$2$$$ to achieve the maximal Fibonacciness of $$$3$$$.

In the third test case, it can be shown that $$$2$$$ is the maximum Fibonacciness that can be achieved. This can be done by setting $$$a_3$$$ to $$$18$$$.

Example input:
6
1 1 3 5
1 3 2 1
8 10 28 100
100 1 100 1
1 100 1 100
100 100 100 100

Example output:
3
2
2
1
1
2

Editorial:
Farmer John's Card Game
Contest: Codeforces Round 998 (Div. 3)
Difficulty rating: 1000
Tags: greedy, sortings

Farmer John's $$$n$$$ cows are playing a card game! Farmer John has a deck of $$$n \cdot m$$$ cards numbered from $$$0$$$ to $$$n \cdot m-1$$$. He distributes $$$m$$$ cards to each of his $$$n$$$ cows.

Farmer John wants the game to be fair, so each cow should only be able to play $$$1$$$ card per round. He decides to determine a turn order, determined by a permutation$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n$$$, such that the $$$p_i$$$'th cow will be the $$$i$$$'th cow to place a card on top of the center pile in a round.

In other words, the following events happen in order in each round:

- The $$$p_1$$$'th cow places any card from their deck on top of the center pile.
- The $$$p_2$$$'th cow places any card from their deck on top of the center pile.
- ...
- The $$$p_n$$$'th cow places any card from their deck on top of the center pile.

There is a catch. Initially, the center pile contains a card numbered $$$-1$$$. In order to place a card, the number of the card must be greater than the number of the card on top of the center pile. Then, the newly placed card becomes the top card of the center pile. If a cow cannot place any card in their deck, the game is considered to be lost.

Farmer John wonders: does there exist $$$p$$$ such that it is possible for all of his cows to empty their deck after playing all $$$m$$$ rounds of the game? If so, output any valid $$$p$$$. Otherwise, output $$$-1$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 400$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \cdot m \leq 2\,000$$$) — the number of cows and the number of cards each cow receives.

The following $$$n$$$ lines contain $$$m$$$ integers each – the cards received by each cow. It is guaranteed all given numbers (across all $$$n$$$ lines) are distinct and in the range from $$$0$$$ to $$$n \cdot m - 1$$$, inclusive.

It is guaranteed the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$2\,000$$$.

Output format:
For each test case, output the following on a new line:

- If $$$p$$$ exists, output $$$n$$$ space-separated integers $$$p_1, p_2, \ldots, p_n$$$.
- Otherwise, output $$$-1$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, one turn order that allows all cards to be played is by having the first cow go before the second cow. The cards played will be $$$0\rightarrow1\rightarrow2\rightarrow3\rightarrow4\rightarrow5$$$.

In the second test case, there is only one cow, so having the cow play all of her cards in increasing order will empty the deck.

In the third test case, it can be shown there is no valid turn order that allows all cards to be played.

Example input:
4
2 3
0 4 2
1 5 3
1 1
0
2 2
1 2
0 3
4 1
1
2
0
3

Example output:
1 2
1
-1
3 1 2 4

Editorial:
Game of Mathletes
Contest: Codeforces Round 998 (Div. 3)
Difficulty rating: 900
Tags: games, greedy, sortings, two pointers

Alice and Bob are playing a game. There are $$$n$$$ ($$$n$$$ is even) integers written on a blackboard, represented by $$$x_1, x_2, \ldots, x_n$$$. There is also a given integer $$$k$$$ and an integer score that is initially $$$0$$$. The game lasts for $$$\frac{n}{2}$$$ turns, in which the following events happen sequentially:

- Alice selects an integer from the blackboard and erases it. Let's call Alice's chosen integer $$$a$$$.
- Bob selects an integer from the blackboard and erases it. Let's call Bob's chosen integer $$$b$$$.
- If $$$a+b=k$$$, add $$$1$$$ to score.

Alice is playing to minimize the score while Bob is playing to maximize the score. Assuming both players use optimal strategies, what is the score after the game ends?

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 2\cdot 10^5, 1 \leq k \leq 2\cdot n$$$, $$$n$$$ is even).

The second line of each test case contains $$$n$$$ integers $$$x_1,x_2,\ldots,x_n$$$ ($$$1 \leq x_i \leq n$$$) — the integers on the blackboard.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output the score if both players play optimally.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, one way the game may go is as follows:

- Alice selects $$$1$$$ and Bob selects $$$3$$$. The score increases as $$$1+3=4$$$. Now the two integers remaining on the blackboard are $$$2$$$ and $$$2$$$.
- Alice and Bob both select $$$2$$$. The score increases as $$$2+2=4$$$.
- The game ends as the blackboard now has no integers.

In the third test case, it is impossible for the sum of Alice and Bob's selected integers to be $$$1$$$, so we answer $$$0$$$.

Note that this is just an example of how the game may proceed for demonstration purposes. This may not be Alice or Bob's most optimal strategies.

Example input:
4
4 4
1 2 3 2
8 15
1 2 3 4 5 6 7 8
6 1
1 1 1 1 1 1
16 9
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3

Example output:
2
1
0
4

Editorial:
Subtract Min Sort
Contest: Codeforces Round 998 (Div. 3)
Difficulty rating: 1100
Tags: greedy

You are given a sequence $$$a$$$ consisting of $$$n$$$ positive integers.

You can perform the following operation any number of times.

- Select an index $$$i$$$ ($$$1 \le i < n$$$), and subtract $$$\min(a_i,a_{i+1})$$$ from both $$$a_i$$$ and $$$a_{i+1}$$$.

Determine if it is possible to make the sequence non-decreasing by using the operation any number of times.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line of each test case contains $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
If it is possible to make the sequence non-decreasing, print "YES" on a new line. Otherwise, print "NO" on a new line.

You can output the answer in any case. For example, the strings "yEs", "yes", and "Yes" will also be recognized as positive responses.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the array is already sorted.

In the second test case, we can show that it is impossible.

In the third test case, after performing an operation on $$$i=1$$$, the array becomes $$$[0,1,2,3]$$$, which is now in nondecreasing order.

Example input:
5
5
1 2 3 4 5
4
4 3 2 1
4
4 5 2 3
8
4 5 4 5 4 5 4 5
9
9 9 8 2 4 4 3 5 3

Example output:
YES
NO
YES
YES
NO

Editorial:
Graph Composition
Contest: Codeforces Round 998 (Div. 3)
Difficulty rating: 1500
Tags: dfs and similar, dsu, graphs, greedy

You are given two simple undirected graphs $$$F$$$ and $$$G$$$ with $$$n$$$ vertices. $$$F$$$ has $$$m_1$$$ edges while $$$G$$$ has $$$m_2$$$ edges. You may perform one of the following two types of operations any number of times:

- Select two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq n$$$) such that there is an edge between $$$u$$$ and $$$v$$$ in $$$F$$$. Then, remove that edge from $$$F$$$.
- Select two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq n$$$) such that there is no edge between $$$u$$$ and $$$v$$$ in $$$F$$$. Then, add an edge between $$$u$$$ and $$$v$$$ in $$$F$$$.

Determine the minimum number of operations required such that for all integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq n$$$), there is a path from $$$u$$$ to $$$v$$$ in $$$F$$$ if and only if there is a path from $$$u$$$ to $$$v$$$ in $$$G$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of independent test cases.

The first line of each test case contains three integers $$$n$$$, $$$m_1$$$, and $$$m_2$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$, $$$0 \leq m_1,m_2 \leq 2\cdot 10^5$$$) — the number of vertices, the number of edges in $$$F$$$, and the number of edges in $$$G$$$.

The following $$$m_1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v\leq n$$$) — there is an edge between $$$u$$$ and $$$v$$$ in $$$F$$$. It is guaranteed that there are no repeated edges or self loops.

The following $$$m_2$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v\leq n$$$) — there is an edge between $$$u$$$ and $$$v$$$ in $$$G$$$. It is guaranteed that there are no repeated edges or self loops.

It is guaranteed that the sum of $$$n$$$, the sum of $$$m_1$$$, and the sum of $$$m_2$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer denoting the minimum operations required on a new line.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case you can perform the following three operations:

1. Add an edge between vertex $$$1$$$ and vertex $$$3$$$.
2. Remove the edge between vertex $$$1$$$ and vertex $$$2$$$.
3. Remove the edge between vertex $$$2$$$ and vertex $$$3$$$.

In the second test case, $$$F$$$ and $$$G$$$ already fulfill the condition in the beginning.

In the fifth test case, the edges from $$$1$$$ to $$$3$$$ and from $$$2$$$ to $$$3$$$ must both be removed.

Example input:
5
3 2 1
1 2
2 3
1 3
2 1 1
1 2
1 2
3 2 0
3 2
1 2
1 0 0
3 3 1
1 2
1 3
2 3
1 2

Example output:
3
0
2
0
2

Editorial:
Multiplicative Arrays
Contest: Codeforces Round 998 (Div. 3)
Difficulty rating: 2200
Tags: combinatorics, dp, number theory

You're given integers $$$k$$$ and $$$n$$$. For each integer $$$x$$$ from $$$1$$$ to $$$k$$$, count the number of integer arrays $$$a$$$ such that all of the following are satisfied:

- $$$1 \leq |a| \leq n$$$ where $$$|a|$$$ represents the length of $$$a$$$.
- $$$1 \leq a_i \leq k$$$ for all $$$1 \leq i \leq |a|$$$.
- $$$a_1 \times a_2 \times \dots \times a_{|a|}=x$$$ (i.e., the product of all elements is $$$x$$$).

Note that two arrays $$$b$$$ and $$$c$$$ are different if either their lengths are different, or if there exists an index $$$1 \leq i \leq |b|$$$ such that $$$b_i\neq c_i$$$.

Output the answer modulo $$$998\,244\,353$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t\leq 10^3$$$) — the number of independent test cases.

The only line of each test case contains two integers $$$k$$$ and $$$n$$$ ($$$1 \leq k \leq 10^5, 1\leq n \leq 9\cdot 10^8$$$).

It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output $$$k$$$ space-separated integers on a new line: the number of arrays for $$$x=1,2,\ldots,k$$$, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test case, there are $$$2$$$ arrays $$$a$$$ with $$$|a|\leq 2$$$ and the product of elements equal to $$$1$$$:

- $$$[1]$$$
- $$$[1,1]$$$

There are $$$3$$$ arrays $$$a$$$ with $$$|a|\leq 2$$$ and the product of elements equal to $$$2$$$:

- $$$[2]$$$
- $$$[1,2]$$$
- $$$[2,1]$$$

Example input:
3
2 2
4 3
10 6969420

Example output:
2 3
3 6 6 10
6969420 124188773 124188773 729965558 124188773 337497990 124188773 50981194 729965558 337497990

Editorial: