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\)