Long Long Strings

Time limit1sMemory limit512 MB

Summary

Decide whether two sequences of insertions and deletions, applied to any sufficiently long string, produce identical results.

Level: Hard8 of 10
Topics: String, Math, Implementation, Simulation
Solved: No attempts yet

Problem

To store long DNA sequences, a company built a LongLongString class that holds strings of more than ten billion characters. The class supports two operations.

Ins(p, c): insert the character $c$ at position $p$ .
Del(p): delete the character at position $p$ .

A DNA editing program is a sequence of Ins and Del operations. Write a program that decides whether two DNA editing programs are identical, meaning that applying them to any sufficiently long string always gives the same result. For example:

Del(1) Del(2) and Del(3) Del(1) are identical.
Del(2) Del(1) and Del(1) Del(2) are different.
A program with no operations and Ins(1, X) Del(1) are identical.
Ins(14, B) Ins(14, A) and Ins(14, A) Ins(15, B) are identical.
Ins(14, A) Ins(15, B) and Ins(14, B) Ins(15, A) are different.

Input

The input holds two DNA editing programs. Each program has between 0 and 2,000 operations, one operation per line. The first character of a line is D for a Del operation, I for an Ins operation, or E for the end of that program.

A D line holds D, a space, and the position of the character to delete. The position is an integer between 1 and $10^{10}$ . Every character after the deleted one moves one position lower.

An I line holds I, a space, the position where the new character goes, another space, and the character itself, which is an uppercase letter. The character already at that position and everything after it move one position higher.

Output

Print 0 on a single line if the two programs are identical, and 1 otherwise.

Examples5

Example 1
Input
```
D 1
D 2
E
D 3
D 1
E
```
Expected output
```
0
```
Example 2
Input
```
D 2
D 1
E
D 1
D 2
E
```
Expected output
```
1
```
Example 3
Input
```
I 1 X
D 1
E
E
```
Expected output
```
0
```
Example 4
Input
```
I 14 B
I 14 A
E
I 14 A
I 15 B
E
```
Expected output
```
0
```
Example 5
Input
```
I 14 A
I 15 B
E
I 14 B
I 15 A
E
```
Expected output
```
1
```