SP6895 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.._q_-1.

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_.

The only one line contains _q_ integers _MaxEdge_(_P_ $ ^{0} $ ),..,_MaxEdge_(_P $ ^{q} $_ $ ^{-1} $ ), separated by a single space.