aliens

Problem Description

There have been many reported crop circle sightings recently.

We have classified crop circles into 10 types, from 0 to 9.

Scientists conjecture that if the same type of crop circle appears in the same location for a large number of consecutive sightings, then we will be not alone in this universe.

We want you to help the scientists by telling them the maximum number of consecutive sightings of any type of crop circle in a specified area.

Region Names do not contain spaces and are case sensitive and within 100 characters.

Input

The first line of the input contains one integer, the number of queries N.

For the next N lines, each line consists of a string, the region of sighting, followed by a number, 1 or 2. 1 indicates a new reported sighting. If 1, 1 will be followed by an additional integer from 0 to 9 indicating the type of crop circle sighted. If 2, the scientists are asking for the largest consecutive sequence of any type of crop circle reported within that region.

NOTE: You will never be asked query 2 unless there is a reported sighting in the area.

Constraints

N <= 1,000,000

Output

For every query number 2, you are required to output a single line containing the maximum number of consecutive sightings of a crop circle of any type in that region.

NOTE: There will be at least one query number 2.

Subtasks

Subtask 1 (30%) All sightings and queries will be from 1 location, all other constraints apply.

Subtask 2 (20%) N <= 1000, all other constraints apply.

Subtask 3 (50%) All above constraints apply.

Sample Testcase 1

Input

4
SouthAmerica 1 0
SouthAmerica 1 0
SouthAmerica 1 0
SouthAmerica 2

3

Explanation

There are three consecutive reports of crop circle 0 in SouthAmerica.

Sample Testcase 2

Input

6
Singapore 1 0
Singapore 1 1
Singapore 1 1
Singapore 1 0
America 1 9
Singapore 2

2

Explanation

Singapore has sightings of crop circle types 0,1,1,0 in order, hence maximum consecutive sighting is 2 (1,1).