Ringo's Fate Transfer

Ringo is on a mission! She must travel by train across the icy world with n stations (numbered 1 through n) to find Shyouma and complete the fateful transfer. Each station i is assigned two labels: c_i and d_i.

There are two types of trains available:

• Regular Trains: There is a bidirectional regular train between any two distinct stations i and j. The travel time between them is computed as $$\min\Bigl(a_{c_i \mathbin{|} c_j},\,b_{d_i \mathbin{\&} d_j}\Bigr),$$ where | denotes the bitwise OR and & denotes the bitwise AND. It is guaranteed that the array a is monotone non-decreasing and b is monotone non-increasing.
• Express Trains: There are m one‐way express train routes. The i^th express train goes from station u_i to station v_i with travel time w_i.

Ringo starts at station 1 but does not know where destiny awaits. For every station, if Shyouma happens to be there, determine the minimum time Ringo needs to reach that station.

inputFormat

The first line contains four integers n, A, B, and m:

• n: number of stations.
• A: the length of array a.
• B: the length of array b.
• m: number of express train routes.

The second line contains A integers, representing the array a (monotone non-decreasing).

The third line contains B integers, representing the array b (monotone non-increasing).

The fourth line contains n integers: c₁, c₂, ... , c_n (each in the range [0, A-1]).

The fifth line contains n integers: d₁, d₂, ... , d_n (each in the range [0, B-1]).

Then, m lines follow. Each line contains three integers u, v and w (1-based station indices) describing an express train from station u to station v with travel time w.

You may assume that a regular train exists between any two distinct stations with a travel cost computed as

$$\min\Bigl(a_{c_i \mathbin{|} c_j},\,b_{d_i \mathbin{\&} d_j}\Bigr). $$

outputFormat

Output a single line with n space-separated integers, where the i^th integer is the minimum time required to travel from station 1 to station i. If a station is unreachable, output -1 for that station.

sample

3 4 4 1
1 3 5 7
10 6 2 1
0 1 2
3 2 1
1 3 1

0 2 1