혀끝에 맴도는 단어

혹시 이런 상황을 겪어 본 적 있나요? 즐겁게 대화하다가 수백 번 써 온 단어를 말하려는데 그 단어가 떠오르지 않아서, 첫 음절에서 말이 막혀 버리는 상황 말입니다. 대화 중의 공백을 없애는 연구소(ICPC)는 이 문제를 줄여 주는 소프트웨어를 만들었습니다.

단어가 혀끝에 맴돌 때는 그 단어의 앞부분 몇 글자를 소프트웨어에 입력합니다. 그러면 사전에서 그 글자로 시작하는 단어가 몇 개인지 알려 줍니다. ICPC는 많은 고객이 단어의 끝부분만 기억나는 '혀뿌리 문제'도 겪는다는 사실을 알게 되었습니다. 소프트웨어는 다음 질의를 지원해야 합니다.

AND $p$ $s$는 접두사가 $p$이고 접미사가 $s$인 사전 단어의 개수를 셉니다. OR $p$ $s$는 접두사가 $p$이거나 접미사가 $s$인 단어의 개수를 셉니다. XOR $p$ $s$는 접두사가 $p$이거나 접미사가 $s$이지만, 둘 다에 해당하지는 않는 단어의 개수를 셉니다.

접두사와 접미사는 단어 전체가 될 수 있고, 한 단어 안에서 서로 겹칠 수도 있습니다. ICPC 소프트웨어의 특이한 점 때문에 $p$와 $s$의 길이는 반드시 같아야 합니다. 들어오는 모든 질의에 답하세요.

첫 줄에 두 정수 $n$과 $q$ ($1 \le n,q \le 2 \cdot 10^5$)가 주어집니다. $n$은 사전에 있는 단어의 수이고, $q$는 질의의 수입니다.

다음 $n$개 줄에는 사전의 단어 $w$가 한 줄에 하나씩 주어집니다. 다음 $q$개 줄에는 세 문자열 $o$, $p$, $s$가 주어집니다. $o$는 AND, OR, XOR 중 하나이고, $p$와 $s$는 1글자 이상의 소문자 알파벳으로 이루어진 문자열이며 $|p| = |s|$입니다.

사전 단어와 질의에 담긴 문자의 총합은 $10^6$을 넘지 않습니다. 이 합계에는 연산 이름, 공백, 줄바꿈이 포함되지 않습니다. 즉, 입력에 등장하는 소문자는 최대 $10^6$개입니다. 사전의 단어는 모두 서로 다릅니다.

질의마다 한 줄씩, 주어진 순서대로 답을 출력합니다. 각 줄에는 해당 질의에 맞는 사전 단어의 개수를 정수 하나로 출력합니다.