For a directed graph G where any vertex v has two weights A_v and B_v, we call A_u+B_v the weight of a edge (u,v). Let MaxEdge(G) be the maximum weight of the edges of G.

Given a permutation P on 1..n, we can derive a directed graph G=(V,E) where V={1,..,n} and (u,v) in E iff P(u)=v. Your task is to compute MaxEdge(P^k) for every k in 0..q-1.

Input

The first line contains a positive integer n.
The second line contains n integers in {1,..,n}, denoting the permutation P.
The third and the fourth line both contain n natural numbers, A₁,..,A_n and B₁,..,B_n respectively.
The fifth line contains a positive integer q.

Output

The only one line contains q integers MaxEdge(P⁰),..,MaxEdge(P^q-1), separated by a single space.

Example

Input:
3
3 2 1
0 1 2
2 2 0
5

Output:
3 4 3 4 3

Constraint

n <= 66000
A_i, B_i <= 16
q <= 10⁶

Notice

The time limit is somehow strict. Please do not spoil the problem with a cheating solution.

Description updated on 2010-7-11