Snapshot Array

You are required to implement a Snapshot Array, a data structure that supports taking snapshots of an array and retrieving historical versions of its elements.

The data structure supports the following commands:

• init X: Initializes the Snapshot Array with length X. All elements are initially 0.
• set i val: Sets the element at index i to val in the current snapshot.
• snap: Takes a snapshot of the array and returns the snapshot id. The snapshot id is the number of times snap has been called, starting from 0.
• get i snap_id: Returns the value at index i at the time the snapshot with id snap_id was taken.

For example, consider the following sequence of operations:

init 3
set 0 5
snap        // returns 0
set 0 6
snap        // returns 1
get 0 0    // returns 5

Your task is to process commands from standard input and output the results of the snap and get commands to standard output, each on a new line.

Note: If a value is not set at a specific index for a snapshot, its default value is 0. When processing get, if there is no update for index i at the queried snapshot id, return the value from the latest snapshot before it; if none exists then return 0.

Mathematically, if we denote the snapshot id by \(s\) and an update at index \(i\) with value \(v\) at snapshot \(t\) (where \(t \le s\)) is recorded, the answer for get i s is \(v\) corresponding to the greatest \(t\) such that \(t \le s\). If there is no such \(t\), then the answer is \(0\).

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains an integer Q representing the total number of commands.
• The next Q lines each contain a command. Commands can be one of the following four types:
  • init X
  • set i val
  • snap
  • get i snap_id

Commands are processed in the order they are given. It is guaranteed that the first command will always be an init command.

outputFormat

For every snap command, output the returned snapshot id on a new line. For every get command, output the corresponding value on a new line. The output should be written to standard output (stdout).

## sample

6
init 3
set 0 5
snap
set 0 6
snap
get 0 1

0
1
6

</p>