题目背景

译自 Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection) D2T1。$\texttt{1s,0.5G}$。

祝 NaCly_Fish 生日快乐！（2024.7.28）

受洛谷评测系统的限制（本题需要 run-twice），本题无法评测。

题目描述

给定 $N$ 对 $[1,10^9]$ 间的正整数，类似于 C++ 中的 $\texttt{std::map<int,int>}$，可以把每对数的第一个数看成「键」（key），第二个数看成「值」（value）。保证键两两不同，可以通过键查询值。

你想要发送这 $N$ 对正整数，但是受带宽限制，只能将这 $N$ 对正整数压缩成一个 $\texttt{01}$ 串来发送。

写一个程序，将这 $N$ 对正整数压缩成 $\texttt{01}$ 串；或者给定你构造的 $\texttt{01}$ 串，$Q$ 次询问给定键，你要回答对应的值。

输入格式

第一行，一个正整数 $T\in \{1,2\}$，表示数据类型：若为 $1$，则为编码操作；否则为解码操作。

• 当 $T=1$ 时：

第二行，一个整数 $N$，代表正整数对数；

接下来 $N$ 行，每行两个正整数 $x_i,y_i$，分别表示键和对应的值。

• 当 $T=2$ 时：

第二行，三个正整数 $N,Q,K$，表示正整数对数，询问次数和 $\texttt{01}$ 串长度；

第三行，一个长度为 $K$ 的 $\texttt{01}$ 串。

接下来 $Q$ 行，每行一个正整数 $x_i$，表示询问的键。

输出格式

• 当 $T=1$ 时：

第一行，一个正整数 $K$，表示你构造的 $\texttt{01}$ 串长度；

第二行，你构造的 $\texttt{01}$ 串。

• 当 $T=2$ 时：

输出 $Q$ 行，每行一个正整数，表示对应的值。

1
3
2 10
3 3
5 7

7
1100111

2
3 2 7
1100111
5
3

7
3

提示

数据范围

对于 $100\%$ 的数据，保证：

• $T\in \{1,2\}$；
• $1\le N,Q\le 100$，$1\le K\le 6\, 000$；
• $1\le x_i,y_i\le 10^9$；
• $x_i$ 两两不同。

评分方式

如果你的输出格式有错或者没有正确回答询问，得 $0$ 分。

否则记 $K$ 为你输出的 $\texttt{01}$ 串长度，得分由下表确定：

$K$	得分
$K\gt 6\, 000$	$0$
$3\, 000\le K\le 6\, 000$	$\displaystyle 100- \frac{K-3\, 000}{30}$
$K\le 3\, 000$	$100$