一节数学课上,几位大佬因教学内容过于简单,偷偷开始了聊天,为了彰显他们的智慧,他们的聊天内容都经过了加密。信息是二进制的,共有 $M$($1≤M≤50000$)条,侦察能力很强的老师已经拦截了部分的聊天内容,知道了第 i 条二进制信息的前 $b_i$ ($1≤b_i ≤10000$)位,他同时知道,学生们使用 $N$($1≤N≤50000$)条暗号.但是,他仅仅知道第 $j$ 条暗号的前 $c_j$($1≤c_j ≤10000$)位。
对于每条暗号 j,他想知道有多少截得的聊天能够和它匹配。也就是说,有多少信息和这条暗号有着相同的前缀。当然,这个前缀长度必须等于暗号和那条信息长度的较小者。
在输入文件中,信息位数的总数(即 $\sum b_i + \sum c_i$)不会超过 $500000$。