Quantum

A research team is developing a new way of storing and manipulating data on magnetic disks. The method lets quantum operations act on the sectors of a disk. Each quantum operation costs a certain amount of energy, and the more energy the storage unit consumes, the warmer it gets. Given a set of available quantum operations and their costs, write a program that computes the lowest possible total cost of transforming a given binary word into a desired binary word.

A binary word has length $1 \le L \le 20$. Every quantum operation is a string of the same length $L$, built from the four letters:

• N — does nothing (leaves the bit unchanged);
• F — flips (inverts) the bit;
• S — sets the bit to 1;
• C — resets the bit to 0.

The $i$-th letter of an operation acts on the bit at position $i$ of the binary word. Applying an operation transforms every position of the word simultaneously according to its letters. You may apply operations in any order and any number of times. A word is transformed by applying a sequence of operations to it, and the total energy cost equals the sum of the costs of the operations performed. For each requested pair of words, find the minimum total cost to turn the first word into the second, or report that it is impossible.

The first line contains a single integer $N$ ($1 \le N \le 20$), the number of test cases. Each test case is given as follows:

• One line with three integers $L$, $\mathit{nop}$ and $\mathit{nw}$ separated by single spaces, where $L$ ($1 \le L \le 20$) is the length of the binary words and operations, $\mathit{nop}$ ($\mathit{nop} \le 32$) is the number of available quantum operations, and $\mathit{nw}$ ($\mathit{nw} \le 20$) is the number of binary words to transform.
• Then $\mathit{nop}$ lines follow, each containing the definition of one quantum operation (a string of length $L$ over N, F, S, C) and its energy cost $c_i$ ($0 \le c_i \le 1000$), separated by a single space.
• Then $\mathit{nw}$ lines follow, each containing two binary words of length $L$ separated by a single space. The first word must, when possible, be transformed into the second using the available operations. Binary words are written as sequences of 0s and 1s.

For each test case, print one line listing the minimum energy cost of transforming each binary word, in the same order as the input, separated by single spaces. If a binary word cannot be transformed into its target, print NP (not possible) in its place instead of a cost.