In-Memory Database with Backup and Restore

Implement SET key value, GET key, DELETE key, BACKUP, and RESTORE id. SET overwrites and outputs OK; GET outputs the value or NULL; DELETE deletes the key and outputs OK if it exists, otherwise NULL. BACKUP saves the current state and outputs an ID that increases from 1 and is never reused; RESTORE with a valid ID restores that state and outputs OK, while an invalid ID outputs NULL and leaves the state unchanged. Old backups can always be restored, and later modifications must not corrupt a backup. Backup and restore must avoid copying the whole database.

输入格式

The first line contains the number of commands n, followed by n lines of commands, 1≤n≤200000. In the original problem, strings are non-empty and contain no whitespace, with no length limit; on this site each key/value is 1 to 64 Unicode characters (each at most 4 UTF-8 bytes), the total input is ≤16MiB, and RESTORE IDs range from 0 to 200000.

输出格式

Each command outputs exactly one line. NULL is also a valid stored value and must not be mistaken for a missing key.

样例 1

输入：

7
SET a 1
BACKUP
SET a 2
GET a
RESTORE 1
GET a
DELETE a

输出：

OK
1
OK
2
OK
1
OK

样例 2

输入：

9
BACKUP
SET a NULL
BACKUP
DELETE a
RESTORE 2
DELETE a
DELETE a
RESTORE 1
GET a

输出：

1
OK
2
OK
OK
OK
NULL
OK
NULL

样例 3

输入：

10
SET x one
BACKUP
SET x two
BACKUP
RESTORE 1
SET x three
RESTORE 2
GET x
RESTORE 9
GET x

输出：

OK
1
OK
2
OK
OK
OK
two
NULL
two

样例说明

Example 1 reads 1 after restoring. In example 2 the string NULL really exists, so the first deletion returns OK and only the second returns NULL. In example 3, restoring an old version and then modifying it does not affect backup 2, and an invalid restore does not change the current value either.