Background

Little E is a first-grade elementary school 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 will understand this number as $353,\!442,\!899$.

However, this does not affect her communication—she just cannot read the text on paper. The only problem is that she is now going to learn division with remainder, and the teacher might draw some red crosses on the paper. But so what?

Problem Description

For a digit-only string $s=s_1s_2s_3\cdots s_n$ of length $n$, define its value as $f(s)=\sum\limits_{i=1}^n 10^{n-i}s_i$ (that is, the decimal number it represents). Define its reversed string as $\overline s=s_ns_{n-1}s_{n-2}\cdots s_1$. For example, for $s=\texttt{0321}$, its value is $f(s)=321$, and its reversed string is $\overline s=\texttt{1230}$.

Construct a string $s$ such that $|s|\le 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 guarantee that $s_1\neq \texttt0$ and $s_n\neq \texttt 0$.

If there is no solution, output the integer $-1$ only.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, indicating the number of test cases.

The second line contains an integer $c$, with the meaning described in the statement.

The next $T$ lines each contain two natural numbers $a, b$ separated by a space, describing one test case.

Output Format

Output $T$ lines. Each line contains a positive integer representing the number you constructed.

This problem uses Special Judge. As long as your output meets the requirements, you can get the score for that test point.

4
0
1755648 1755648
0 353442899
35281 18253
99728538 70320626

1000000001
998244353
35281
66330831785160880538172878128228067748679057340064161580956433229228884846388176250309226257600174873157935217529307119972759542770571505108922703815887608877795159689067116959276902444827654683066165

1
1
30 30

030

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

4509169566936302030543528193
6765800751328156020889260421
6754420765703935546785979321
4408846009459835952892074437
3108033793065515131695113495

Hint

Sample Explanation

For the first test case in the sample, $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 feasible solution.

Constraints and Notes

This problem uses bundled subtasks.

A slash in the table means there are no special restrictions.

For $100\%$ of the testdata, $1\leq T\leq 30$, $c\in\{0,1\}$, $0 \leq a, b \lt 998{,}244{,}353$。

Translated by ChatGPT 5