There $N$ people in your city. The $j^{th}$ person contains $A_j$ health point. You are trying to make these people walk in your locality. You walk for $M$ days. On the $i^{th}$ day, every walk decreases $B_i$ health points of the person you are walking with. Also, on the $i^{th}$ day, you can only walk with the $j^{th}$ person if the person is still healthy and $j$ is a multiple of $i$. You can walk with as many people as you can but you can walk with a specific person only once in a day.

A person becomes unhealthy if their health point becomes less than or equal to $0$. At the end of each day, their health points are restored to their original level if they are not unhealthy already.

Your task is to determine the day in which the $i^{th}$ person becomes unhealthy or will remain healthy.

Input format

• First line: $T$ denoting the number of test cases
• For each test case:
  • First line: Contains two integers $N$ and $M$ denoting the number of people and days on which you walk respectively
  • Next line: $N$ integers where $A_i$ denotes the health points of the $i^{th}$ person
  • Next line: $M$ integers where $B_i$ denotes the reduction of the health of the $i^{th}$ day's walk

Output format
Print $N$ lines where the $i^{th}$ of these​​​​​ lines contain a single integer, denoting the day when the $i^{th}$ person becomes unhealthy. Otherwise, print $-1$ if the $i^{th}$ person never becomes unhealthy.

Constraints

$1 \leq T \leq3$
$1 \leq N, M \leq 10^6$
$1 \leq A_i , B_i\leq 10^9$