P9500 "RiOI-2" tnelat

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?

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.

**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 $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.**

### 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.** | $\text{Subtask}$ | Score | $a,b$ | Special Property | | :--------------: | :---: | :---: | :--------------: | | $0$ | $5$ | $ \in [1, 9]$ | $a = b$ | | $1$ | $10$ | $ \in [0, 9]$ | / | | $2$ | $15$ | $ \in [0, 99]$ | / | | $3$ | $25$ | / | $a = 0$ | | $4$ | $25$ | / | $c = 1$ | | $5$ | $20$ | / | / | 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