Log Ingestion and Query

Append logs in order and run closed-interval queries; service/level match exactly, keyword does a substring match on message, and * means no filter.

This site's standard input/output format and supplementary bounds follow this problem's description.

输入格式

The first line contains q (1≤q≤5000, a bound set by this site to cap the time of direct queries), and each of the next q lines is ADD timestamp service level message or QUERY start end service|* level|* keyword|*. message may contain spaces.

输出格式

For each QUERY, output the number of matches on one line.

样例 1

输入：

6
ADD 1 api INFO hello world
ADD 2 api ERROR failed
QUERY 1 2 * * *
QUERY 1 2 api INFO hello
QUERY 2 2 api ERROR fail
QUERY 3 4 * * *

输出：

2
1
1
0

样例 2

输入：

3
ADD 0 web INFO x
QUERY 0 0 * * *
QUERY 1 2 * * *

输出：

1
0

样例 3

输入：

10
ADD 2 web INFO login failed
ADD 7 web ERR login ok
ADD 10 web ERR bad request
ADD 6 api ERR login failed
ADD 5 web INFO login failed
ADD 7 api ERR bad request
ADD 10 web ERR login failed
QUERY 3 2 * * bad
QUERY 2 6 api * *
QUERY 7 2 web * *

输出：

0
1
0