题目背景

P9500 「RiOI-2」tnelat

小 $\varepsilon$ 是一名 $3^{32}$ 年级的小学生。她正在学习如何阅读。

题目描述

对于一个长度为 $n$ 的由数字组成的字符串 $s=s_1s_2s_3\cdots s_n$，定义它的权值为 $f(s)=\sum\limits_{i=1}^n 10^{n-i}s_i$。（也就是它代表的十进制数）定义它的反串为 $\overline s=s_ns_{n-1}s_{n-2}\cdots s_1$。例如，$s=\texttt{0321}$ 的权值为 $f(s)=321$，反串为 $\overline s=\texttt{1230}$。

给定正整数 $k$，对于若干组给定的 $a,b$，试构造一个非空数字串 $s$，使得 $|s|\le 444$，且 $f(s)\equiv a\pmod {3^k}$ 且 $f(\overline s)\equiv b\pmod {3^k}$。你还要保证 $s_1\neq \texttt0$ 且 $s_n\neq \texttt 0$。

如果无解，仅输出整数 $-1$ 即可。

输入格式

本题有多组数据。

第一行一个正整数 $T$ 表示数据组数。

第二行一个正整数 $k$，意义如题目所述。

接下来 $T$ 行，每行两个以空格隔开的自然数 $a, b$ 描述一组数据。

输出格式

输出 $T$ 行，每行一个字符串表示你构造的 $s$。如果无解，仅输出整数 $-1$ 即可。

本题开启 Special Judge，只要你的输出符合要求即可得到该测试点的分数。

4
4
1 1
5 8
3 12
69 15

1
-1
361425
20120712

3
1
0 0
1 1
2 1

9
1
-1

提示

【样例解释】

对于第一组样例，$3^k=3^4=81$，可以验证 $1\equiv 1,1\equiv 1,361\,425\equiv 3,524\,163\equiv 12,20\,120\,712\equiv 69,21\,702\,102\equiv 15\pmod {81}$，而可以证明不存在非空数字串 $s$ 满足 $s_1\neq \texttt0$，$s_n\neq \texttt 0$，$f(s)\equiv 5\pmod {81}$ 且 $f(\overline s)\equiv 8\pmod {81}$。

【数据范围】

本题开启捆绑测试。

子任务编号	分值	特殊性质
$1$	$2$	$k\le 3$
$2$	$7$	$k\le 7$
$3$	$5$	$k\le 12$
$4$	$13$	$k\le 18$
$5$	$19$	$k\le 25$
$6$	$11$	$T\le 3$
$7$	$17$	$a=0$
$8$	$23$	所有 $a,b$ 在范围内独立均匀随机生成
$9$	$3$	无

对于 $100\%$ 的数据，$1\leq T\leq 10^5$，$1\le k\le 32$，$0\le a,b<3^k$。

【提示】

本题 IO 量较大。

对于 C++ 选手，经过测试，如果每组数据都将字符串完整输出（而不是一个一个输出）在 C++14 (GCC 9) O2 下，使用开了 std::ios_base::sync_with_stdio(false); 的 std::cout 用时不会超过 100ms。如果您想要逐个输出字符，或者更好地优化 IO，可以使用如下的快读模板：

namespace IO{
	const int N=1<<22;
	char buf[N],*p1,*p2;
	char wbuf[N],*pw;
	struct qqq{qqq(){p1=buf;p2=buf;pw=wbuf;}~qqq(){fwrite(wbuf,1,pw-wbuf,stdout);}}q;
	inline char gc(){
		if (p1==p2) p2=(p1=buf)+fread(buf,1,N,stdin);
		return (p1==p2)?EOF:(*p1++);
	}
	long long read(){
		char c=gc();
		long long x=0;
		while(c<'0'||c>'9') c=gc();
		while(c>='0'&&c<='9'){
			x=x*10+(c^'0');
			c=gc();
		}
		return x;
	}
	void push(const char& c){
		if (pw-wbuf==N) fwrite(pw=wbuf,1,N,stdout);
		*pw++=c;
	}
	void write(const std::string&s)
	{
		for(char c:s) push(c);
	}
}

在引用了 <string> 头文件的情况下，使用 IO::read() 可以读入一个 long long 型整数，IO::push(ch) 可以输出一个字符 ch，IO::write(str) 可以输出一个字符串 str。