Vampiric politicians P39136

Statement

In a country far away, some politicians seem to be eternal. After a thorough study, the reason has finally been found out: they are vampires. The cementery where they rest has been located. Can you help to exterminate as many of them as possible, by thrusting a long silver pike vertically through the ground?

0.57 For simplicity, let us consider a two-dimensional world. For each vampire, we know the beginning and the end of its body when resting horizontally in its tomb. All the vampires rest at diferent depths, which are irrelevant.

To the right you can see the first case of the sample. When the four vampires are resting, we can happily kill them all.

0.40

(12,7)

(0,0)(12,0)(12,5)(0,5)

(1,1)(9,1)(9,1.2)(1,1.2)

(3,3)(6,3)(6,3.2)(3,3.2)

(5,2)(11,2)(11,2.2)(5,2.2)

(4,4)(7,4)(7,4.2)(4,4.2)

(5.5,6)(5.5,-1)

Input

Input consists of several cases. Each case starts with the number of vampires $n$ . Follow $n$ triples $s_i, \ell_i, r_i$ , with the name, the left extreme and the right extreme of each vampire when resting. You can assume $1 \le n \le 10^4$ , that all $s_i$ are different and made up of between 1 and 12 lowercase letters, and $0 \le \ell_i < r_i \le 10^9$ .

Follow between 1 and $10^5$ names of vampires. Initially, the cemetery is empty. Each given name $s$ indicates that the vampire $s$ enters the cementery if $s$ was not already there, or that $s$ leaves the cemetery otherwise. The word “END” marks the end of each case.

Output

After each given vampire name $s$ , print the maximum number of vampires that could be killed at that moment. Print a line with 10 dashes at the end of each case.

Public test cases

Input

4
perista 0 8
inconsolable 2 5
bucolica 4 10
camallarg 3 6
perista
bucolica
camallarg
inconsolable
bucolica
END
5
a 0 500000000
b 500000000 1000000000
c 0 499999999
d 23 42
e 0 499999999
b
b
a
b
c
a
e
END

Output

1
2
3
4
3
----------
1
0
1
2
2
1
2
----------

Information

Author: Salvador Roura
Language: English
Official solutions: C++
User solutions: C++