Problem Background

Little E is a first-grade elementary student. She is learning how to read.

If you write $998,244,353$ on paper, she will read it as "three-five-three-four-four-two-eight-nine-nine." Yes, she reads from right to left. Then, she interprets this number as $353,442,899$.

However, this does not affect her communication—she just cannot read text on paper. The only issue is that she is now learning division with remainders, and the teacher might draw some red crosses on paper. But, what does it matter?

Problem Description

For a string \( s = s_1s_2s_3 \cdots s_n \) of length \( n \) consisting of digits, define its weight as \( f(s) = \sum_{i=1}^n 10^{n-i}s_i \) (which is the decimal number it represents). Define its reverse string as \( \overline{s} = s_ns_{n-1}s_{n-2} \cdots s_1 \). For example, if \( s = \texttt{0321} \), then \( f(s) = 321 \) and \( \overline{s} = \texttt{1230} \).

Construct a string \( s \) such that \( |s| \leq 114514 \), and \( f(s) \equiv a \pmod{998,244,353} \) and \( f(\overline{s}) \equiv b \pmod{998,244,353} \). If \( c = 0 \), you must also ensure \( s_1 \neq \texttt{0} \) and \( s_n \neq \texttt{0} \). If there is no solution, output the integer \(-1\).

Input Format

This problem has multiple test cases.

The first line contains a positive integer \( T \) indicating the number of test cases.

The second line contains an integer \( c \), as described in the problem.

The next \( T \) lines, each containing two space-separated natural numbers \( a \) and \( b \), describe a test case.

Output Format

Output \( T \) lines, each containing a positive integer representing the constructed number.

This problem has a Special Judge enabled, so as long as your output meets the requirements, you will receive points for that test case.

Sample Input and Output

Sample Input #1

4
0
1755648 1755648
0 353442899
35281 18253
99728538 70320626

Sample Output #1

1000000001
998244353
35281
66330831785160880538172878128228067748679057340064161580956433229228884846388176250309226257600174873157935217529307119972759542770571505108922703815887608877795159689067116959276902444827654683066165

Sample Input #2

1
1
30 30

Sample Output #2

030

Sample Input #3

5
0
114514191 214748364
414414414 515515515
302813344 124821394
123456789 987654321
307210721 127012703

Sample Output #3

4509169566936302030543528193
6765800751328156020889260421
6754420765703935546785979321
4408846009459835952892074437
3108033793065515131695113495

Notes/Hints

Sample Explanation

For the first sample case's first data, \( s = \overline{s} = \texttt{1000000001} \), \( f(s) = f(\overline{s}) = 1,000,000,001 \equiv 1,755,648 \pmod{998,244,353} \), so it is a valid solution.

Data Size and Constraints

This problem has bundled tests.

The slash in the table indicates no special restrictions.

For 100% of the data, \( 1 \leq T \leq 30 \), \( c \in \{0, 1\} \), \( 0 \leq a, b < 998,244,353 \).

见题面 Input 部分

见题面 Output 部分