ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1678. Space Poker 3

Time limit: 3.0 second
Memory limit: 64 MB
Space poker. A legendary game, first version of which was introduced as far as in year 1284 of Alien era. Even nowadays its rules are known only to small group of professional players. Fortunately, the developers of the first program in the world playing space poker asked for your help.
There are N extraterrestial players in space poker. At the beginning of the round, each player gets M cards (we call them hole cards). Players don't know hole cards of their opponents. Then K community cards are consecutively dealt face-up. So, community cards are known to all players. Player's hand consists of his hole cards and all community cards — M + K cards in total. There are no suits, cards differ only in their values. There are 13 different values: "2", "3", "4", …, "9", "T", "J", "Q", "K" and "A". The card deck is infinite, and the probability of the event that the next card will have a given value is equal to 1/13. The combinations in space poker are represented in the form: (v1, …, vL), where L is the number of different values in the combination. The hand satisfies the combination (v1, …, vL) in case it contains v1 cards of one value, v2 cards of another value, …, vL cards of L-th value. For example, combination (2, 2) is satisfied by hands "2JA2A" and "22233". Combination (2, 3) is satisfied by hand "KQKQKQ" but is not satisfied by hand "AAAAAA". All combinations have different strength. The winner of the round is a player whose hand satisfies the combination of the maximal strength among all combinations in hands of all players. If there is more than one such player, the round ends in a draw.
Suppose you know the hole cards of the first player and partly dealt community cards. Calculate the probability the first player will be the only winner of this round.

Input

The first line contains integers N, M and K separated by spaces (2 ≤ N, M ≤ 10; 1 ≤ K ≤ 5). The second line contains M symbols — hole cards of the first player. The third line contains at most K symbols — dealt community cards. The fourth line contains integer C — the number of combinations in space poker (1 ≤ C ≤ 100). The following C lines contain combinations in order of increasing strength. Each description has the form L v1 v2vL. L and vi are positive integers, sum of all vi doesn't exceed M + K.

Output

Output the probability of winning for the first player with absolute error not exceeding 10−5.

Samples

inputoutput
2 5 2
23456

1
1 2
0.0883526857
2 5 2
23456
78
2
7 1 1 1 1 1 1 1
1 4
0.8407915043
Problem Author: Alex Samsonov
Problem Source: Ural SU Contest. Petrozavodsk Summer Session, August 2008