You are given three permutations a,b,c of length n. Recall that a permutation is a sequence of n integers from 1 to n, in which each number occurs exactly once.
There are three integers x,y and z. Initially, all of them equal to 1. After each second, x,y,z become ay,bz,cx respectively and simultaneously (note that the subscripts arey,z,x}).
You need to answer multiple independent queries. For each query, you are given three integers x′,y′ and z′. Tell Walk Alone the minimum time needed for tuple (x,y,z) to become (x′,y′,z′) if possible.
输入格式
The first contains an integer n (1≤n≤10^5), indicating the length of the permutations.
Each of the next three lines contains n integers. The i-th number of the second line, the third line and the fourth line indicate ai,bi and ci (1≤ai,bi,ci≤n), respectively.
The next line contains an integer Q (1≤Q≤10^5), indicating the number of queries.
Each of the next Q lines contains three integers x′,y′ and z′ (1≤x′,y′,z′≤n).
输出格式
For each query, output the minimum time needed for (x,y,z) to become (x′,y′,z′) in a line, or −1 if impossible.