/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 333 点
問題文
高橋君は図書館の司書として働いており、書棚に並んだ本のタイトルについて利用者からの問い合わせに対応しています。
高橋君が管理する書棚には N 冊の本が一列に並んでおり、左から i 番目の本のタイトルは文字列 S_i です（1 \leq i \leq N）。なお、同じタイトルの本が複数存在することもあります。ある日、青木君が図書館を訪れ、書棚の本について Q 個の問い合わせを行いました。
j 番目の問い合わせ（1 \leq j \leq Q）では、青木君は 2 つの整数 L_j, R_j と 1 つの文字列 T_j を指定します。高橋君は、左から L_j 番目から R_j 番目までの本（両端を含む）の中に、タイトルが文字列として T_j と完全に一致する本が何冊あるかを答えなければなりません。
すべての問い合わせに対する答えを求めてください。
制約
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- N, Q は整数
- S_i は英小文字からなる長さ 1 以上 10 以下の文字列 (1 \leq i \leq N)
- 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
- L_j, R_j は整数
- T_j は英小文字からなる長さ 1 以上 10 以下の文字列 (1 \leq j \leq Q)
入力
N Q S_1 S_2 \ldots S_N L_1 R_1 T_1 L_2 R_2 T_2 \vdots L_Q R_Q T_Q
- 1 行目には、本の冊数 N と問い合わせの数 Q が、スペース区切りで与えられる。
- 2 行目には、書棚に並んだ N 冊の本のタイトル S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
- 続く Q 行のうち j 行目（1 \leq j \leq Q）には、j 番目の問い合わせにおける区間の左端 L_j、右端 R_j、および検索するタイトル T_j が、スペース区切りで与えられる。
出力
Q 行にわたって出力せよ。j 行目（1 \leq j \leq Q）には、j 番目の問い合わせに対する答え、すなわち左から L_j 番目から R_j 番目までの本のうちタイトルが T_j と一致するものの冊数を出力せよ。
入力例 1
5 3 apple banana apple orange apple 1 5 apple 2 4 apple 1 3 grape
出力例 1
3 1 0
入力例 2
8 5 cat dog cat bird dog cat dog cat 1 8 cat 3 6 dog 1 4 bird 5 8 cat 2 2 dog
出力例 2
4 1 1 2 1
入力例 3
15 8 book pen book note pen book desk pen note book lamp pen book note desk 1 15 book 1 15 pen 3 10 book 5 12 pen 1 1 book 7 7 desk 10 15 note 1 15 chair
出力例 3
5 4 3 3 1 1 1 0
Score : 333 pts
Problem Statement
Takahashi works as a librarian and handles inquiries from patrons about the titles of books arranged on a bookshelf.
The bookshelf managed by Takahashi has N books lined up in a row, and the title of the i-th book from the left is the string S_i (1 \leq i \leq N). Note that there may be multiple books with the same title. One day, Aoki visits the library and makes Q inquiries about the books on the bookshelf.
In the j-th inquiry (1 \leq j \leq Q), Aoki specifies two integers L_j, R_j and one string T_j. Takahashi must answer how many books among those from the L_j-th to the R_j-th from the left (inclusive) have a title that exactly matches the string T_j.
Find the answers to all inquiries.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- N, Q are integers
- S_i is a string of lowercase English letters with length between 1 and 10 inclusive (1 \leq i \leq N)
- 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
- L_j, R_j are integers
- T_j is a string of lowercase English letters with length between 1 and 10 inclusive (1 \leq j \leq Q)
Input
N Q S_1 S_2 \ldots S_N L_1 R_1 T_1 L_2 R_2 T_2 \vdots L_Q R_Q T_Q
- The first line contains the number of books N and the number of inquiries Q, separated by a space.
- The second line contains the titles S_1, S_2, \ldots, S_N of the N books on the bookshelf, separated by spaces.
- In the following Q lines, the j-th line (1 \leq j \leq Q) contains the left endpoint L_j, right endpoint R_j of the range, and the title to search for T_j in the j-th inquiry, separated by spaces.
Output
Output Q lines. On the j-th line (1 \leq j \leq Q), output the answer to the j-th inquiry, that is, the number of books from the L_j-th to the R_j-th from the left whose title matches T_j.
Sample Input 1
5 3 apple banana apple orange apple 1 5 apple 2 4 apple 1 3 grape
Sample Output 1
3 1 0
Sample Input 2
8 5 cat dog cat bird dog cat dog cat 1 8 cat 3 6 dog 1 4 bird 5 8 cat 2 2 dog
Sample Output 2
4 1 1 2 1
Sample Input 3
15 8 book pen book note pen book desk pen note book lamp pen book note desk 1 15 book 1 15 pen 3 10 book 5 12 pen 1 1 book 7 7 desk 10 15 note 1 15 chair
Sample Output 3
5 4 3 3 1 1 1 0