#!/usr/bin/env python

from __future__ import division
import math
import itertools
import random
import time
from collections import defaultdict

def top_height(sz):
    """Returns the height of the top part of size `sz' AS-Waksman network."""
    return sz // 2

def bottom_height(sz):
    """Returns the height of the bottom part of size `sz' AS-Waksman
    network."""
    return sz - top_height(sz)

def switch_output(base, pos, sz, top):
    """The recursive AS-Waksman construction AS-Waksman(sz) places two
    lines of floor(sz/2) switches each and connects the outputs of
    AS-Waksman(floor(sz/2)) and AS-Waksman(ceil(sz/2)) in between
    them.

    Return the output wire of left-hand side switch `pos'(relative to
    the base level `base' in the recursive call) in size `sz'
    AS-Waksman network.

    If `top' = True, return the top wire, otherwise return bottom
    wire. """
    relpos = pos - base
    assert relpos % 2 == 0 and relpos + 1 < sz
    if top:
        return base + (relpos // 2)
    else:
        return base + top_height(sz) + (relpos // 2)

def switch_input(base, pos, sz, top):
    """This function is symmetric to switch_output(base, pos, sz, top),
    but returns the input wire of the right-hand side switch (rather than
    the output wire of the left-hand side switch)."""
    # because of symmetry this coincides with switch_output
    return switch_output(base, pos, sz, top)

def width(sz):
    """Returns width of size `sz' AS-Waksman network. For example, width(2) =
    1, width(3) = 3, width(4) = 3."""
    return 2*int(math.ceil(math.log(sz, 2)))-1

def construct_as_waksman_topology(n):
    """Returns a pair (neighbors, switches) describing the topology of
    AS-Waksman network of size n.

    neigbhors[i][j] lists the possible locations where a wire, at
    position j before going through the i-th column, could be routed to
    after passing through the column. neighbors[i][j] is a length 1
    list for straight wires and length 2 list for switches, where the
    first element denotes the destination when the switch is operated
    in "straight" mode and the second element denotes the destination
    for the "cross" mode.

    switches[i] is the dictionary, whose keys are all positions of the
    switches at the i-th column and keys are switch settings. This
    function only returns the topology, so switch settings are all set
    to be None."""

    assert n > 1
    w = width(n)

    neighbors = [{} for i in xrange(w)]
    switches = [{} for i in xrange(w)]

    def construct_as_waksman_topology_inner(left, right, lo, hi, rhs_dests):
        """Construct AS-Waksman subnetwork occupying switch columns [left,
        left+1, ..., right] that will route left-hand side inputs [lo,
        lo+1, ..., hi] to right-hand side destinations rhs_dests[0],
        rhs_dests[1], ..., rhs_dests[hi-lo+1]. (That is, rhs_dests are
        0-indexed w.r.t. base of lo.)

        This function will fill out neighbors[left],
        neighbors[right-1] and add switches in columns switches[left],
        switches[right]."""
        if left > right:
            return

        sz = (hi - lo + 1)
        assert len(rhs_dests) == sz

        assert (right - left + 1) >= width(sz)

        if right - left + 1 > width(sz):
            # If there is more space for the routing network than
            # required, just add straight edges. This also takes care
            # of size 1 routing network base case.
            for i in xrange(lo, hi + 1):
                neighbors[left][i] = [i]
                neighbors[right][i] = [rhs_dests[i - lo]]
            # Recurse to construct the corresponding subnetwork.
            construct_as_waksman_topology_inner(left + 1, right - 1, lo, hi, range(lo, hi+1))
        elif sz == 2:
            # Non-trivial base case: routing a 2-element permutation.
            neighbors[left][lo] = [rhs_dests[0], rhs_dests[1]]
            neighbors[left][hi] = [rhs_dests[1], rhs_dests[0]]
            switches[left][lo] = None
        else:
            # Networks of size sz > 2 are handled by adding two lines
            # of switches alongside the network and recursing.
            new_rhs_dests = [None] * sz

            # This adds floor(sz/2) switches alongside the network. As
            # per AS-Waksman construction one of the switches in the even
            # case can be eliminated (i.e. set to be constant); this
            # will be handled later.
            for i in xrange(lo, hi, 2):
                switches[left][i] = None
                switches[right][i] = None

                neighbors[left][i] = [switch_output(lo, i, sz, True), switch_output(lo, i, sz, False)]
                neighbors[left][i+1] = [switch_output(lo, i, sz, False), switch_output(lo, i, sz, True)]

                new_rhs_dests[switch_input(lo, i, sz, True)-lo] = i
                new_rhs_dests[switch_input(lo, i, sz, False)-lo] = i+1

                neighbors[right][i] = [rhs_dests[i-lo], rhs_dests[i+1-lo]]
                neighbors[right][i+1] = [rhs_dests[i+1-lo], rhs_dests[i-lo]]

            if sz % 2 == 1:
                # Odd special case: the last wire is not connected to
                # any of the switches and just routed straight.
                neighbors[left][hi] = [hi]
                neighbors[right][hi] = [rhs_dests[hi-lo]]
                new_rhs_dests[hi-lo] = hi
            else:
                # Even special case: fix the bottom-most LHS switch to
                # a constant "straight" setting.
                neighbors[left][hi-1] = [switch_output(lo, hi-1, sz, True)]
                neighbors[left][hi] == [switch_output(lo, hi-1, sz, False)]

            d = top_height(sz)
            construct_as_waksman_topology_inner(left + 1, right - 1, lo, lo + d - 1, new_rhs_dests[:d])
            construct_as_waksman_topology_inner(left + 1, right - 1, lo + d, hi, new_rhs_dests[d:])

    construct_as_waksman_topology_inner(0, w-1, 0, n-1, range(n))
    return (neighbors, switches)

def switch_position_from_wire_position(base, global_pos):