Problem H. Homo or Hetero?

Author:ACM ICPC 2009-2010, NEERC, Northern Subregional Contest   Time limit:3 sec
Input file:homo.in   Memory limit:256 Mb
Output file:homo.out  

Statement

Consider a list of numbers with two operations:

For example: the result of the insertion of a number 4 to the list [1, 2, 1] is the list [1, 2, 1, 4]. If we delete the number 1 from this list, we get the list [2, 1, 4], but if we delete the number 3 from the list [1, 2, 1, 4], the list stays unchanged.

The list is homogeneous if it contains at least two equal numbers and the list is heterogeneous if it contains at least two different numbers. For example: the list [2, 2] is homogeneous, the list [2, 1, 4] is heterogeneous, the list [1, 2, 1, 4] is both, and the empty list is neither homogeneous nor heterogeneous.

Write a program that handles a number of the operations insert and delete on the empty list and determines list's homogeneity and heterogeneity after each operation.

Input file format

The first line of the input file contains an integer number n — the number of operations to handle (1 ≤ n ≤ 100 000).

Following n lines contain one operation description each. The operation description consists of a word insert or delete, followed by an integer number k — the operation argument ( − 109 ≤ k ≤ 109).

Output file format

For each operation output a line, containing a single word, describing the state of the list after the operation:

Sample tests

No. Input file (homo.in) Output file (homo.out)
1
11
insert 1
insert 2
insert 1
insert 4
delete 1
delete 3
delete 2
delete 1
insert 4
delete 4
delete 4
neither
hetero
both
both
hetero
hetero
hetero
neither
homo
neither
neither

0.064s 0.010s 13