20618번 - Necklace 다국어

Chiaki has $n$ beautiful gems. The color of the $i$-th gem is $c_i$ and the value is $v_i$.

Chiaki would like to choose at least $3$ gems and make a necklace such that the adjacent gems must have different color. Formally, let the indices of gems used in the necklace be $a_1,a_2,\ldots,a_m$ ($m \ge 3$) in clockwise order. For each $i$ ($1 \le i \le m$), $c_{a_i}$ should be different from $c_{a_{i \bmod m + 1}}$.

Chiaki would like to find a necklace with the maximum possible sum of values: that is, to maximize $\sum\limits_{i=1}^{m} v_{a_i}$.

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$): the number of gems.

The second line contains $n$ integers $c_1,c_2,\ldots,c_n$ ($1 \le c_i \le n$) denoting the color of each gem.

The third line contains $n$ integers $v_1,v_2,\ldots,v_n$ ($-10^9 \le v_i \le 10^9$) denoting the value of each gem.

It is guaranteed that the sum of $n$ in all test cases does not exceed $2 \cdot 10^5$.

For each test case, the first line contains an integer $m$ ($m \ge 3)$: the number of gems in the necklace (note that you don't need to maximize it). The second line contains $m$ integers $a_1,a_2,\ldots,a_m$ ($1 \le a_i \le n$): the indices of gems used in the necklace in clockwise order. If there are several possible answers, print any one of them.

If Chiaki could not find such a necklace, just output an integer $-1$ on a single line.