Chrono Key Timeline Store

A telemetry store keeps a timeline of string values for each key. It processes q operations, each one of:

• SET key val t — record that at time t, key key held value val. For any fixed key, the SET operations arrive with strictly increasing timestamps.
• GET key t — report the value that key held at the greatest recorded time that is less than or equal to t. If the key has no recorded value at a time <= t, report *.

Keys and values are non-empty tokens of lowercase letters and digits.

Input format

Line 1: an integer q. Next q lines: SET key val t or GET key t.

Output format

For each GET operation, in order, print the resolved value, or * if none applies.

Constraints

• 1 <= q <= 40
• 0 <= t <= 1000000
• 1 <= length of key, val <= 12