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 restrictions of the Luogu judging system (this problem requires run-twice), it is unjudgeable.

Problem Description

Given \( N \) pairs of positive integers within the range \([1, 10^9]\), similar to \(\texttt{std::map<int, int>}\) in C++, each pair can be viewed as a key and its corresponding value. The keys are guaranteed to be unique and can be used to query their values.

You want to transmit these \( N \) pairs of integers, but due to bandwidth limitations, you can only send them as a \(\texttt{01}\) string after compression.

Write a program that compresses these \( N \) pairs of integers into a \(\texttt{01}\) string; or given your constructed \(\texttt{01}\) string, answer \( Q \) queries for a given key and return the corresponding value.

Input Format

The first line contains a positive integer \( T \in \{1, 2\} \), indicating the type of data: if \( T = 1 \), it is an encoding operation; otherwise, it is a decoding operation.

• When \( T = 1 \):

The second line contains an integer \( N \), representing the number of pairs of positive integers.

The next \( N \) lines each contain two positive integers \( x_i, y_i \), representing the key and its corresponding value.

• When \( T = 2 \):

The second line contains three positive integers \( N, Q, K \), representing the number of pairs of positive integers, 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 a positive integer \( x_i \), representing the key to be queried.

Output Format

• When \( T = 1 \):

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

The second line contains the constructed \(\texttt{01}\) string.

• When \( T = 2 \):

Output \( Q \) lines, each containing a positive integer, representing the corresponding value.

Sample Input and Output

Sample Input #1

1
3
2 10
3 3
5 7

Sample Output #1

7
1100111

Sample Input #2

2
3 2 7
1100111
5
3

Sample Output #2

7
3

Notes

Data Range

For \( 100\% \) of the data, it is guaranteed that:

• \( T \in \{0, 1\} \);
• \( 1 \le N, Q \le 100 \), \( 1 \le K \le 6,000 \);
• \( 1 \le x_i, y_i \le 10^9 \);
• \( x_i \) are unique.

Scoring Method

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

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

见题面 Input 部分

见题面 Output 部分