Background

Translated from Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection) D2T1. $\texttt{1s,0.5G}$.

Happy birthday to NaCly_Fish! (2024.7.28)

Due to limitations of the Luogu judging system (this problem requires run-twice), this problem cannot be judged.

Problem Description

You are given $N$ pairs of positive integers in $[1,10^9]$. Similar to $\texttt{std::map<int,int>}$ in C++, you can treat the first number of each pair as a "key" and the second number as a "value". It is guaranteed that all keys are distinct, and you can query the value by its key.

You want to send these $N$ pairs of positive integers, but due to bandwidth limits, you can only compress them into a $\texttt{01}$ string for transmission.

Write a program to compress these $N$ pairs of positive integers into a $\texttt{01}$ string; or, given the $\texttt{01}$ string you constructed, answer $Q$ queries: for each given key, you must output the corresponding value.

Input Format

The first line contains a positive integer $T\in \{1,2\}$, indicating the data type. If $T=1$, it is an encoding task; otherwise, it is a decoding task.

• When $T=1$:

The second line contains an integer $N$, the number of pairs.

The next $N$ lines each contain two positive integers $x_i,y_i$, representing the key and the corresponding value.

• When $T=2$:

The second line contains three positive integers $N,Q,K$, representing the number of pairs, the number of queries, and the length of the $\texttt{01}$ string.

The third line contains a $\texttt{01}$ string of length $K$.

The next $Q$ lines each contain one positive integer $x_i$, the queried key.

Output Format

• When $T=1$:

The first line contains a positive integer $K$, the length of the $\texttt{01}$ string you constructed.

The second line contains the $\texttt{01}$ string you constructed.

• When $T=2$:

Output $Q$ lines, each containing one positive integer, the corresponding value.

1
3
2 10
3 3
5 7

7
1100111

2
3 2 7
1100111
5
3

7
3

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that:

• $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$.
• All $x_i$ are pairwise distinct.

Scoring

If your output format is incorrect or you do not answer the queries correctly, you get $0$ points.

Otherwise, let $K$ be the length of the $\texttt{01}$ string you output. Your score is determined by the following table:

Translated by ChatGPT 5