Carried Off by a Visitor

A guide robot in a ring-shaped exhibition hall was confidently localized when a visitor lifted it up and set it down somewhere else. This is the kidnapped robot problem: the robot's belief is sure and wrong. The hall is a ring of n cells (after cell n - 1 comes cell 0), with a "door" or a "wall" beside each cell, as given in world. The robot's belief after it was put down is belief (probabilities that add up to 1).

A filter that allows probability 0 can never come back to a cell it ruled out: zero times any likelihood is still zero. So after every step the robot mixes a little uniform belief back in:

with \varepsilon = eps, as if it allowed for a fresh kidnapping in every step.

The robot makes the steps, each a pair (u, reading). In each step, in this order:

1. Move u cells forward: it ends up u - 1, u or u + 1 cells further on with probabilities p_under, p_exact, p_over (they add up to 1), wrapping round the ring.
2. Sense: the sensor reports reading, the true side of its cell with probability p_correct and the other one otherwise. Update with Bayes' rule and normalise.
3. Mix in the uniform belief as above.

After each step, the best guess is the cell with the largest probability; cells within 1e-9 of the largest count as tied, and the smallest index among them wins.

Write recover(world, belief, steps, p_under, p_exact, p_over, p_correct, eps) that returns the list of best guesses, one per step.

Examples

Input:  world = ["door", "wall", "wall", "door", "wall", "wall", "wall", "door", "wall", "wall"],
        belief = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        steps = [(1, "wall"), (1, "door"), (1, "wall"), (1, "wall"), (1, "door"),
                 (1, "wall"), (1, "wall"), (1, "door"), (1, "wall"), (1, "wall")],
        p_under = 0, p_exact = 1, p_over = 0, p_correct = 0.9, eps = 0
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
Explanation: the robot believes it starts in cell 0 but was put down in cell 5, so it is
really in cells 6, 7, 8, 9, 0, 1, 2, 3, 4, 5. Without mixing, it can only ever be in the
cell it believes, and every reading that disagrees is put down to sensor noise.

Input:  the same, but eps = 0.05
Output: [1, 2, 3, 4, 0, 1, 2, 3, 4, 5]
Explanation: by the fifth step the readings outweigh the old belief; from then on the
best guess is the true cell.

Constraints

• answers are compared exactly

Goals

• Mix a small uniform probability into the belief after every step
• See why a belief with zeros can never recover from being wrong
• Follow the best guess as evidence overturns a confident mistake