Ledger Snapshot Recall

A ledger holds an array of n integer cells, indexed 0 to n-1, all starting at 0. It processes q operations, each one of:

• SET i val — set cell i to val in the live array.
• SNAP — take a snapshot of the whole live array. Snapshots are numbered from in the order they are taken; report the id assigned to this snapshot.

A snapshot captures the effect of every SET performed before it (including sets made after earlier snapshots).

Input format

Line 1: two integers n and q. Next q lines: SET i val, SNAP, or GET i s.

Output format

For every SNAP (print the assigned id) and every GET (print the recalled value), in order, print one value per line.

Constraints

• 1 <= n <= 20
• 1 <= q <= 40
• 0 <= i < n
• -1000000 <= val <= 1000000