TopCoder

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

49.0% (24/49)

Tags

Description

有玩過Monster Galaxy嗎?
話說曾經身為Tentacle War第一粉絲的阿ˋ蚯,
最近在某種能量貨幣的循循善誘下打算轉戰Monster Galaxy。
如此天大的轉變傳遍各地,甚至驚動了Monster Galaxy的開發者。

為了盛大的迎接阿ˋ蚯,開發者打算對Monster Galaxy大改版。
新加入的玩家不再能自行選擇第一隻Moga,而另有規則。
開發者挑出了 n 種Moga,對每種都賦予一個字串 S 與優先度 P ,
而每個新玩家加入時也會被隨機賦與一個字串 K 。
一個Moga可能成為此玩家的第一隻Moga若且唯若 K 是 S 的子字串。
而一個玩家的第一隻Moga就是所有可能Moga中優先度最高的。

然而由於阿ˋ蚯的轉戰引起玩Monster Galaxy的風潮,
不按算法的開發者想不出方法快速的幫如此多人找出第一隻Moga。
最後不得已,只好將問題外包給你。

你能夠幫開發者盛大的迎接阿ˋ蚯嗎?

Input Format

第一行有兩個數字 n, m 代表挑出 n 種Moga,而共有 m 個新玩家。
接下來有 m 行,第 i 行包含一個字串 Ki 。
再來有 n 行,第 j 行包含一個字串 Sj 與正整數 Pj ,以空格分開。

1 <= Pj <= 230
1 <= n, m <= 100000
1 <= Σ(Sj), Σ(Ki) <= 2000000
保證每種Moga的優先度都不同。
保證 Sj 與 Ki 中只會出現小寫英文字母。

Output Format

請對每個玩家輸出一行正整數,
代表他的第一隻Moga是第幾種Moga。
如果找不到任何符合的Moga, 請輸出0。

Sample Input

3 4
ro
oo
ee
zzz
weero 1
paroot 2
boogaleef 3

Sample Output

2
3
3
0

Hints

Problem Source

原TIOJ1723 / Problem Setter : worm

Subtasks

For Testdata: 0 ~ 0, Score: 33
For Testdata: 1 ~ 1, Score: 33
For Testdata: 2 ~ 2, Score: 34
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 4000 196608 262144
1 4000 262144 262144
2 4000 262144 262144