Subsequence Probability Game

In this problem, there are \(n\) players and a magical machine. Each player is assigned a unique letter sequence of length \(l\), and every letter in these sequences is chosen from the first \(m\) uppercase letters (so there are \(m\) different letters in total). For example, if \(m=3\) and \(l=4\), then sequences such as ABAA and CBCA are legal, and no two players share the same sequence.

The machine works as follows: at each time step it randomly produces a letter. The probability that the \(i\)th letter appears is given by \(\frac{p_i}{q_i}\) (with \(\sum_{i=1}^m\frac{p_i}{q_i}=1\)). After \(T\) time steps, the machine will have produced a letter sequence of length \(T\).

A player wins if, at some moment, his/her sequence appears as a contiguous substring in the machine’s sequence. As soon as any player's sequence is found, the game stops and that player is declared the winner. The problem is to calculate, for each player, the probability that he/she wins the game.

Note: All formulas are written in \(\LaTeX\) format. You can assume that \(n, m, l, T\) and the letters probabilities are such that a dynamic programming solution with the Aho–Corasick automaton is feasible.

inputFormat

The input consists of several lines:

1. The first line contains four integers: \(n\), \(m\), \(l\) and \(T\) where
   • \(n\): number of players,
   • \(m\): number of different letters (the letters are the first \(m\) uppercase letters),
   • \(l\): the length of each player's sequence,
   • \(T\): the total number of letters produced by the machine.
2. Then \(n\) lines follow, each containing a string of length \(l\) representing the sequence of a player. All sequences are distinct.
3. Then \(m\) lines follow. The \(i\)th of these lines contains two integers \(p_i\) and \(q_i\), representing that the probability of the \(i\)th letter appearing is \(\frac{p_i}{q_i}\) (the letters are in order from 'A' onward).

You may assume that \(\sum_{i=1}^m \frac{p_i}{q_i}=1\).

outputFormat

Output a single line. For each player, in the input order, output his/her winning probability. The probabilities should be printed as floating-point numbers with at least 10 digits after the decimal point, separated by a space.

sample

2 3 4 6
ABAA
CBCA
1 2
1 4
1 4

0.0953125000 0.0171875000