Background

TheBigFatDuck: I'm planning to participate in the American Mathematical Modeling Contest. Do you want to join me?

TheHamster: I'd love to, but I'm not sure how to prepare.

TheBigFatDuck: I can tell you about my preparation plan, blabla... (500 words omitted)

TheHamster: Alright, I trust you. Let's work on the math modeling together.

Description

TheBigFatDuck and TheHamster are participating in a mathematical modeling competition together. They are preparing for Problem C, which is based on a game called Wordle. In simple terms, the rules of this game are as follows:

• At the beginning of each day, the computer randomly selects a 5-letter word as the target word for all players to guess.
• Each round involves players making guesses, and the computer providing feedback.
• In the next round, players need to make new guesses based on the feedback from the computer, continuing until they guess the word chosen by the computer.

The feedback in this game is given as colors for each position of the player's guessed word:

• If the color is green, it means that the guess is completely correct at that position, i.e., the letter in the target word at that position matches the letter in the player's guess.
• If the color is yellow, it means that the guess is partially correct at that position, i.e., the letter in the player's guess exists in the target word, but not at that position.
• If the color is red, it means that the guess is completely incorrect at that position, i.e., the letter at that position in the player's guess does not exist in the target word.
• Note : There is one point in this problem different from the original game, If you got two yellow for two same letters, you can only conclude that the letter is exist and it's position is neither. You can't conclude that the target word have this letter for at least 2 times.

The problem provides the daily words, the number of players participating, and the number of guesses each player makes. The task is to predict the game results for a future day or for a specific word.

TheHamster: Assuming you are a player in this game, how do you plan to play?

TheBigFatDuck: For the first round, I'll randomly choose a word. After receiving feedback, we'll narrow down the candidate words that meet the criteria and randomly choose a word from the candidate set.

TheHamster: (✧◡✧) That's exactly what I was thinking! You can write the code, and I'll work on the paper.

Format

Input

The first line contains two integers, $n$ and $m$, separated by a space, representing the size of the word set and the number of queries. $(1 \le n,m\le 10^5)$

The next $n$ lines each contain a 5-letter string, representing the published word set from which the target word and player's guesses must be selected.

The following $m$ lines each contain two 5-letter strings $s$ and $e$, representing the start of the i-th round of the game (each round has a different target word), where the first guess is $s$, and the feedback is $e$. The task is to determine how many candidate words satisfy the given feedback.

Output

There are $m$ lines in total, each containing a single number $cnt_i$, representing the number of candidate words that satisfy the criteria for the i-th query.

Sample

5 3
fecdf
tycde
ceadb
abcde
xyedc
xyedc rrygy
abcde ggggg
fecdf ryggr

3
1
2

Round #1:

target    =  abcde
guess     =  xyedc
feedback  =  rrygy

3 words fecdf, abcde, ceadb matches the feedback.

Round #2

target    =  abcde
guess     =  abcde
feedback  =  ggggg

1 word abcde matches the feedback.

Round #3

target    =  tycde
guess     =  fecdf
feedback  =  ryggr

2 word abcde, tycde matches the feedback.

Limitations

2 seconds, 256 MB

---

Three months later, the results of the competition were announced, and they received an S award (S means successful participate).

TheBigFatDuck: I'm sorry, I didn't prepare well during the winter vacation, so I didn't achieve good results.

TheHamster: It's okay. I don't really care about the results. I only care about being with you. Besides, you still rank 1st in our class. From now on, Let's work harder.