Finding Her

When she and I go to a department store, we wander the shops separately. Which shop should I check to meet her along the way? She does not want to be interrupted by her phone ringing while shopping, so she keeps it turned off.

We want to write a program that, for a given time, shows the probability that she is in each shop.

The input is a finite graph and a positive integer. The graph models her movement, and the movement occurs in steps of 10 minutes. The positive integer is how many 10-minute intervals have passed since we got separated in the department store. A node of the graph means a shop, an arrow between nodes means a move from one shop to another, and a probability for that move is written on the arrow. A node may have several arrows going out, and the probabilities written on those arrows must sum to 1. The first shop she visits after entering the department store is chosen uniformly at random among the given shops.

For example, if the graph is

then from shop A she always goes to shop B, from shop B she moves to shop C with probability 30%, and so on.

In this case, if she starts shopping from a random shop, the probability that she is in each shop after 10 minutes is A 15%, B 25%, C 7.5%, D 52.5%. After 20 minutes the probabilities are 4.5%, 15%, 7.5%, 73%, respectively.

Write a program that computes results like the above. Assume the shops are the four fixed ones (A, B, C, D). The input is the graph of her movement among the stores and the shopping time (unit: 10 minutes).

The first line gives the shopping time (unit: 10 minutes). The shopping time is a positive integer less than or equal to 10.

The second line gives the number of edges M. (1 ≤ M ≤ 10)

The next M lines give the edge information. Each edge is described by its starting shop, ending shop, and probability.

For each shop A, B, C, D, output the probability that she is there, in percent. The absolute/relative error is allowed up to 10-2.