Safe

Time limit1sMemory limit1024 MB

Summary

Two equal-length numbers get digits appended and removed from the right, and each query asks for one digit of their sum.

Level: Medium7 of 10
Topics: Stack, Math
Solved: No attempts yet

Problem

Archaeologists found a safe on an old ship. Its digital lock has a screen that shows two integers of equal length, and these numbers change from time to time. The screen changes in three ways:

One digit is appended to the right of each number.
Some number of digits disappears from the right of both numbers.
A third number appears on the screen, next to an input field that takes a single digit.

The researchers suspect that the safe opens when you enter the digit of the sum of the two large numbers at the position given by the third number. The numbers change too fast to compute by hand, so they need a program that answers these queries.

The main component is a library that reacts to events on the safe's screen. The functions below are called $N$ times in total.

Function	Description
`void Add(int f, int s)`	Digit f was appended to the right of the first long number, and digit s was appended to the right of the second.
`void Del(int k)`	k digits were removed from the right of both long numbers. You may assume that both long numbers have at least k digits when this function is called. It is possible that no digits remain in them.
`int Get(int p)`	The third number p appeared on the screen. The function must return the digit at position p from the right in the sum of the two long numbers. You may assume that the sum has at least p digits when this function is called.

The test environment provides example files where the required functions are already declared, so you only need to write the implementations in your solution. You may also write your own functions in the solution file. The language is C++ and the solution file is seif.cpp. To compile and test on your own computer, use the following commands.

g++ -o main main.cpp seif.cpp
./main

A sample grader is provided for local testing. The server uses a different grader that also checks whether the answers returned by your solution are correct.

Input

The first line of the input file contains the number of library function calls $N$ ( $1 \le N \le 10^6$ ). Each of the next $N$ lines describes one call in one of the following forms.

1 F S ( $1 \le F \le 9$ , $1 \le S \le 9$ ) is the call Add(f, s).
2 K ( $1 \le K$ ) is the call Del(k).
3 P ( $1 \le P$ ) is the call Get(p).

Output

The output file contains a log of the interaction between the grader and the library.

Examples2

Example 1

Input

Expected output

add(1, 1)
get(1) = 2
add(3, 9)
get(1) = 2
get(2) = 3

Example 2

Input

Expected output

add(1, 1)
add(2, 2)
add(3, 3)
get(1) = 6
get(2) = 4
get(3) = 2
del(2)
add(4, 6)
get(1) = 0
get(2) = 3