C. 猜字母王 Hexguesser

愛麗絲和鮑伯正在玩一個叫「猜字母王」的新遊戲：

在遊戲開始時，鮑伯會想 個從 a 至 f 間可能重覆的字母，例如 或 ，字母是沒有順序的。然後，愛麗絲會開始猜測鮑伯的字母。愛麗絲每次會猜測 個字母，而鮑伯會回應，以 o 標示正確猜測的字母和以 x 標示錯誤猜測的字母。注意字母的順序不需考慮，猜測中的字母會被標示為正確，當且僅當該字母在鮑伯的字母中出現。

例如，如果鮑伯的字母為 和愛麗絲的猜測為 ，那鮑伯其中一個可能的回應為 ，因為其中 個字母 e 為正確猜測，而其他 個字母是不正確的。另外，鮑伯也可以回應 。

愛麗絲和鮑伯以重覆猜測 次，因而產生 個猜測字符串和 個回應字符串。這 組字符串以 表示。現在，有 個其他玩家進入。第 個玩家只能看到第 至第 組字符串。

愛麗絲和鮑伯想知道，每個玩家可以從給定的資訊中推斷出多少個正確的字母。你可以假設玩家們可以足夠聰明地有效運用給定資訊。

Alice and Bob play a brand-new game called \textit{hexguesser}:

At the beginning of the game, Bob thinks of possibly repeated letters from a to f, such as or , with no specific order. After that, Alice can make guesses on Bob's letters. Alice guesses letters each time and Bob will give a response, marking the letters guessed correctly as o and the letters guessed incorrectly as x. Note that the order of the letters does not matter, the guess is considered correct if that letter appears in Bob's letters.

For example, if Bob's letters are and Alice's guess is , then one of the possible responses by Bob is , since of the letter e are correct guesses, while the other letters are incorrect. Alternatively, is also a possible response by Bob.

Alice and Bob have repeated this guessing times, resulting in guess strings and response strings. These pairs of strings are numbered from . Now, other players come in. The -th player can only see the -th to the -th pair of strings.

Alice and Bob wonder how many correct letters each player can deduce with only the given information. You may assume the players are smart enough to utilize the given information.

輸入第一行含有兩個整數 和 。

接下來 行包含 對愛麗絲和鮑伯之間的猜測和回應字符串。回應字符串緊接於對應的猜測字符串。

接下來 行各含有兩個正整數 和 。

The first line of input contains two integers and .

The next lines of input consist of the guess-response pairs between Alice and Bob, with the response string immediately following its corresponding guess string.

The next lines each contains two integers and .

輸出 行。第 行含有一個整數，代表第 個玩家可以推斷出的正確字母數量。如果沒有任何字符串符合第 個玩家看到的猜測和回應（即第 個玩家發現資訊有誤），輸出整數 。

Output lines. The -th line contains a single integer, the number of correct letters the -th player can deduce. If there are no possible strings that satisfy all guess-response pairs seen by the -th player (equivalently, the -th player can deduce that there is wrong information), output the integer .

Sample 1 input

2 2
aabbcc
oxoxox
dddeee
ooxxxx
1 1
1 2

Sample 1 output

3
6

Sample 2 input

2 1
abcdef
oooooo
abcdee
oooooo
1 2

Sample 2 output

-1

Sample explanation

對於樣例測試一的第一個詢問，該玩家可以推斷出鮑伯的字母中包含 。他沒有足夠資訊推斷餘下三個字母中的任何一個。

對於樣例測試一的第二個詢問，該玩家可以推斷出鮑伯的字母是 。

For the first query in sample test 1, the player can only deduce that Bob's letters contain . There is insufficient information to deduce any of the other 3 letters.

For the second query in sample test 1, the player can deduce that the letters are .

對於全部測試數據，滿足：，。 所有輸入字母皆在 a 至 f 之間。

For all test cases, , .

All input letters are within a to f.