MEPPERM  Maximum Edge of Powers of Permutation
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..q1.
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_{1},..,A_{n} and B_{1},..,B_{n} respectively.
The fifth line contains a positive integer q.
Output
The only one line contains q integers MaxEdge(P^{0}),..,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^{6}
Notice
The time limit is somehow strict. Please do not spoil the problem with a cheating solution.
Description updated on 2010711
hide comments
Tony Beta Lambda:
20130903 15:15:50
That complexity being said, you need to optimize for a variety of cases to get it accepted. 

Anton Lunyov:
20100820 20:50:11
What meaning of natural numbers here?


Serge:
20110606 08:49:25
Re: O(max{A_i,B_i}*nlogn) regardless of q Last edit: 20100805 14:15:52 
Added by:  Lox 
Date:  20100701 
Time limit:  1s3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  Own problem 