Luffy Will Become the Pirate King

Edgedancer CUET CSE Fest 2022 - Inte...
Limits 1s, 512 MB

Whitebeard is testing Luffy to see if he can become the Pirate King. Whitebeard has given Luffy three arrays a,b,ca, b, c of length nn and an integer xx. Initially x=1x = 1. Luffy initially has score of 00 and can perform the following operation at most nn time:

  • Select 1in1\leq i \leq n such that ii has not been selected in previous operations and update xx by multiplying it with aia_i that is assign x=x×aix = x \times a_i. If the updated xx is even then add bib_i to the score or if updated xx is odd then add cic_i to the score.

Luffy wants to maximize his score. So, he is asking for your help. Help Luffy become the pirate king.

Input

The input consists of multiple test cases. The first line contains a single integer T(1T4×104)T(1 \leq T \leq 4 \times 10{^4}) — the number of test cases.

Each test case starts with n(1n2×105)n (1\leq n \leq 2 \times 10^{5}) and then three lines follow.

The second line of the test case contains nn integers ai(1ai106)a_i (1 \leq a_i \leq 10^6).

Third line of the test case contains nn integers bi(109bi109)b_i (-10^9 \leq b_i \leq 10^9).

Fourth line of the test case contains nn integers ci(109ci109)c_i (-10^9 \leq c_i \leq 10^9).

Sum of nn of all test cases does not exceed 2×1052 \times 10^{5}.

Output

For each test case, output the maximum score Luffy can obtain if he performs the operations optimally.

Sample

InputOutput
2
3
1 3 5
4 3 1
10 5 8
2
1 2
1 2
2 1
23
4

Submit

Login to submit.

Statistics

52% Solution Ratio
KnightshadeEarliest, 1M ago
S_SubrataFastest, 0.1s
shimul12614Lightest, 5.7 MB
sourav63Shortest, 1091B
Toph uses cookies. By continuing you agree to our Cookie Policy.