DAGame Insane

우”영”이와 현”철”이는 영철버거 돈 마리네 세트를 걸고 내기를 한다. 현철이는 제2회 MatKor Cup의 DAGame에서 다음과 같은 게임을 만들었다.

$N$개의 노드와 $M$개의 간선으로 이루어진 DAG(사이클이 없는 방향 그래프)가 있다. $K$개의 말이 각각 노드 중 하나에 놓여 있다. 모든 노드마다 놓을 수 있는 말의 개수에는 제한이 없으며, 각각의 말은 색깔을 가지고 있다. 또한, 각 노드는 $0$번부터 $N-1$번의 번호를 가지며, 각 색깔은 $0$ 이상 $32$ 미만의 정수로 표현된다. 모든 색깔에 대하여 특정 색깔을 가진 말은 최대 두 개뿐이다. 우영이부터 차례를 번갈아 가며 다음 행동을 취한다.

한 개의 말을 선택하여 그래프 상에서 나가는 방향의 간선을 골라 다음 노드로 옮긴다.
같은 색깔의 말이 같은 노드에 존재하는 순간 서로 업혀 다음 이동부터 같이 움직이게 되고, 색이 다른 말끼리는 항상 영향을 주지 않는다.

게임 시작 전부터 말이 업히는 경우가 존재할 수도 있다. 자신의 차례에 더 이상 행동을 할 수 없는 사람이 지게 된다.

이 내기가 고려대학교의 명물이 되자, 영철버거를 찾는 손님들이 누가 이길지를 두고 내기를 하기 시작했다. 하지만 언제나 정답을 예측할 수 있으므로 불공평하다는 단점이 있었다.

이를 알게 된 현철이는 제3회 MatKor Cup의 DAGame Extreme에서 각 말의 위치를 색깔에 따라 다른 암호를 사용하여 암호화하였다. 하지만 본인이 만든 암호를 우영이가 너무나 쉽게 풀어버려 더 복잡하게 바꾸었다.

현철이는 이번에도 각 말의 위치를 색깔에 따라 다른 암호를 사용하여 암호화하였으며, 색깔 $c$에 대응하는 암호는 $H_0(c)$와 $H_1(c)$을 통해 표현할 수 있다. 여기서 $H_0(c)$와 $H_1(c)$는 각각 $32$ 미만의 음이 아닌 정수로 이루어진 길이 $256$의 배열이며, 각각의 $i$번째 원소를 $H_0(c)[i]$, $H_1(c)[i]$로 표현한다. 또한 암호를 정하기 위해 정해진 $A$가 필요한데, $A$는 $256$행 $32$열(각각 $0$행, $0$열 부터 시작한다)의 정수 배열로, $i$번째 행 $A_i$는 각각 $0$ 이상 $32$ 미만의 정수로 이루어진 순열(모든 원소가 정확하게 $1$번 존재하는 배열)이다. 여기서 $A_i$의 $j$열 원소를 $A_i[j]$라고 한다.

현철이는 어떤 순열을 이용하여 암호화할지 고를 수 있는데, 어떤 말의 위치가 $v$, 색깔이 $c$일 때, 이 정보를 $i$번째 순열을 이용해 암호화하면, $E_i(v,c) =A_i[v\oplus H_0(c)[i]]\oplus H_1(c)[i]$의 식을 통해 암호화된다. 여기서 $\oplus$는 비트 단위 XOR 연산자이다.

또한 현철이는 연속된 여러 개의 순열을 통해 암호화를 여러 번 할 수 있다. 이 경우 이전 순열을 통해 암호화한 결과를 다음 순열을 통한 암호화의 입력으로 사용한다. 즉, 최종적으로 $t$번째 말이 $v_t$번 정점에 있고, $c_t$번 색을 가질 때, 이 정보를 $i$번 순열부터 $j(\ge i)$번 순열까지를 활용하여 암호화하면 $E[t] =E_j\left( E_{j-1}\left( \cdots\left( E_{i+1}\left( E_i\left( v_t,c_t \right),c_t \right),c_t\right),\cdots\right),c_t \right)$의 정수가 나오게 된다.

현철이는 게임 하나가 주어지면, 암호화에 사용할 연속한 순열들을 정한 뒤, 모든 말에 대해 같은 순열을 적용하여 암호화한다.

현철이는 초기 말의 상태를 보고 이를 암호화한다. 이후 선공인 우영이에게 게임을 플레이할 DAG, 각 말들의 색과 암호화된 정보를 알려준다. 우영이는 현철이의 컴퓨터를 해킹해 암호문에 사용하는 순열들의 정보를 알아냈다. 또한 현철이가 해킹에 대비하여 매 게임을 시작하기 전, $256$개의 순열 $A_i$들 중 하나를 골라 다른 순열로 업데이트한다는 것을 알아내었으며, 어떤 순열을 바꾸는지도 알아내었다. 또한 현철이가 $A_i$ 중 하나를 업데이트하면, 현철이의 최첨단 암호화 시스템은 전 자동으로 $H_0$와 $H_1$의 모든 배열을 무작위로 다시 설정한다. 그러나, $H$에 대한 정보는 알아내지 못하였다. 이때 현철이가 매 게임이 시작하기 전 업데이트한 정보는 이후 게임에도 계속 유지된다.

우영이는 이 정보를 통해 두 명 모두 최선의 전략으로 게임을 했을 때, 선공인 자신이 이길 확률을 구하고자 한다. 우영이가 이길 확률은 다음과 같이 정해진다.

DAG와 게임의 말들의 색이 정해졌을 때, 각 말이 각 칸에 위치할 확률은 동일하며, 말의 위치는 서로 독립적으로 정해진다고 하자. 즉, 말의 초기 상태에 대한 총 $N^K$ 가지의 초기 상태에 대해 확률이 모두 같다고 하자.
암호문을 결정하는 $H_0$, $H_1$에 대하여, 총 $32$가지의 색깔에 대해 독립적으로, $H_0$, $H_1$ 각각 $256$개의 $32$미만의 음이 아닌 정수를 정할 확률이 같다고 가정하자. 즉, 색 하나당 $H_0$, $H_1$이 각각 $32^{256}=2^{1280}$ 가지 경우의 수를 가지며, 즉, 총 $\left( \left( 2^{1280} \right)^2 \right)^{32}=2^{81920}$가지의 $H$에 대해 확률이 모두 같다고 하자.

즉, 총 $2^{81920}N^K$가지의 경우의 수 중 주어진 암호문을 만들어 내는 경우의 수를 $X$, 이 중 두 사람 모두 최선의 플레이를 할 때, 우영이가 이기는 경우의 수를 $Y$라고 할 때, $\frac{Y}{X}$을 우영이가 이길 확률이라 한다.

이제 우영이와 현철이는 이 게임을 총 $Q$번 할 것이다. 각 게임마다 우영이가 이길 확률을 구해보자.

첫 번째 줄부터 256번째 줄까지 현철이가 고른 초기 순열들 $A$의 정보가 주어진다. $i$번째 줄에는 $A_{i-1}$의 원소 $32$개가 공백으로 구분되어 순서대로 주어진다. 각각의 줄은 $0$ 이상 $32$ 미만의 수들로 이루어진 순열이다.

다음 줄에 우영이와 현철이가 할 게임의 수 $Q$가 주어진다. $(1\le Q\le 256)$

다음 줄 부터 $Q$개의 게임에 대한 정보가 주어진다.

각 게임의 첫 번째 줄에는 이번 게임을 시작하기 전 현철이가 바꿀 순열의 번호 $l$이 주어진다. $(0\le l<256)$

다음 줄에는 현철이가 이번 게임을 시작하기 전 바꿀 순열을 나타내는 원소 $32$개가 공백으로 구분되어 순서대로 주어진다. 이 수들은 $0$ 이상 $32$ 미만의 수들로 이루어진 순열이다. 현철이는 $A_l$을 이 순열로 바꾼다.

다음 줄에는 현철이가 이번 게임을 암호화하기 위해 사용할 연속된 순열의 시작과 끝 번호를 나타내는 $x$와 $y$가 공백으로 구분되어 주어진다. 현철이는 이번 게임에 $A_x$부터 $A_y$까지 차례로 사용하여 암호화한다. $(0\le x\le y\lt 256)$

다음 줄에는 이번 게임에 사용할 그래프의 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. $(1\le N\le 32;$ $0\le M\le 4\, 096)$

다음 $M$개의 줄에는 이번 게임에 사용할 그래프의 간선을 나타내는 서로 다른 두 정수 $p$와 $q$가 공백으로 구분되어 주어지며 이는 $p$번 노드에서 $q$번 노드로 가는 간선이 존재한다는 것을 뜻한다. 어떤 $p$와 $q$에 대해서 $p$번 노드와 $q$번 노드를 잇는 동일한 간선이 여러 개 존재할 수도 있다. 주어지는 그래프는 DAG(Directed acyclic graph, 유향 비순환 그래프)이다. $(0\le p,q\le N-1;$ $p\ne q)$

다음 줄에는 이번 게임에 사용할 말의 개수를 나타내는 정수 $K$가 주어진다. $(1\le K\le 64)$

다음 $K$개의 줄에는 이번 게임에 사용할 말들의 색깔과 암호화된 정보를 나타내는 두 정수 $c_i$와 $E[i]$가 공백으로 구분되어 주어진다. $(0\le c_i,E[i] <32)$

문제

입력

출력