Given a list of unique employee ids and their age information, your task is to design a program to support the certain operations. Broadly speaking there are two operations, Insert and Query. You can assume that insert operations are unique on the employee_id column. Query operations are of 3 types. Both insert and query operations are described below.

1. A {employee_id} {age} 
    Operation will add the employee_id and age.
    Syntax: A {employee_id} {age}
    Returns: None

2. Q 1 {employee_id} 
    Query will search for the records whose employee id is {user_employee_id}.
    Syntax: Q 1 {employee_id}
    Returns: Boolean (True or False)

3. Q 2 {employee_id} 
    Query will search for the records whose employee id starts with {user_employee_id}.
    Syntax: Q 2 {employee_id}
    Returns: Total count of the records which matches the search criteria.

4. Q 3 {employee_id} {lb} {ub}
    Query will search for the records for which employee id starts with {user_employee_id} and age is in the range (lb, ub).
    Syntax: Q 3 {employee_id} {lb} {ub}
    Returns: Total count of the records which matches the search criteria.

Input Format: 
Every input line consists of either Add (A) or Query (Q) operation. -1 represents the end of input.

Output Format: 
Print the total number of resultant records in case of Query operation.

Constraints:
1 <= Total digits in the Employee ID <= 50
20 <= Age <= 100
10 <=lb<= 100, where lb is a multiple of 10.
lb <=ub<= 100, where ub is a multiple of 10.
Total number of add operations <= 40000
Total number of query operations <= 40000

Sample Input and Output

Input

Output

A 112345 20
A 112346 40
A 212347 40
A 212348 23
A 112449 30
Q 1 112345
Q 2 1123
Q 3 112 10 50
-1

True
2
3

NOTE: 
Minimum time required for evaluating this program is 24 seconds. Please be patient. Request you to wait up to a few minutes before resubmitting the same solution.