Legendary JBNU

Yun Junha, a legendary programmer, built his own database system named JBNU (Jeong Bo Neoh Um).

One JBNU record is a pair: a Key that you use to find the record, and a Value that holds its contents. You need the Key to reach the data you want.

Junha is so forgetful that he kept losing keys. So he reworked JBNU to accept a Key that is not stored and answer with the stored Key closest to it.

Keys and Values are always integers. The closest Key is the stored Key whose difference from the given Key is smallest. To keep the answers accurate, a stored Key whose difference is larger than $K$ is not accepted as a candidate.

Seunggyun, an expert at copying other people's projects, decided to imitate JBNU for his database class. Junha is a legend, so there is no way to get hold of the program he wrote, and Seunggyun wants to hand the work to you, his teammate.

Given the initial contents of JBNU, write a program that supports adding, updating, and searching records.

The first line has the number of initial records $N(1 \le N \le 100{,}000)$, the number of commands $M(1 \le M \le 100{,}000)$, and the distance limit to the closest Key $K(1 \le K \le 10{,}000)$.

Each of the next $N$ lines has the Key and the Value of one initial record. Every Key and every Value is a non-negative integer at most $1{,}000{,}000{,}000$. No two records share a Key.

Each of the next $M$ lines has one of the three commands below.

• 1 Key Value: add a record with the given Key and Value. The input never adds a Key that already exists.
• 2 Key Value: search with the given Key and replace the Value of the record found with the given Value. If no unique Key satisfies the condition, ignore this command.
• 3 Key: search with the given Key and print the record found.

A search works like this. Among the stored Keys, only those whose difference from the given Key is at most $K$ are candidates, and the candidate with the smallest difference is chosen. If two candidates share the smallest difference, the search result is not unique.

For each 3 command, print the result on its own line.

If the search result is unique, print the Value of that record. If no Key has a difference of at most $K$, print -1. If two Keys share the smallest difference, print ?.