Description

After escaping the Magical Corridor, you realize your ordeal is far from over—there’s a second challenge, and KenKenKen’s relentless pursuit continues.

This time, however, his curse has weakened. The restriction on your bag—limiting you to carrying only one gem of each color—has vanished!

Now, you can collect as many gems of any color as you wish, but your objective remains unchanged:

• For a given position m, collect the maximum number of distinct gem colors possible.
• Among all collections with the maximum distinct colors, maximize the total weight of the gems you collect.

The magical movement rules are still in effect:

• If you are at position i, you can only move to positions that are multiples of i. For example, if you are at position 1, you can move to positions 2,3,…,N. From position 2, you can only move to positions 4,6,…

Can you use this newfound freedom to outsmart KenKenKen and finally escape? Your cunning and strategy will decide your fate.

Input

The first line contains two integers N and Q, the length of the corridor and the number of queries.

The second line contains N integers C₁,C₂,...,C_N , where C_i represents the color of the gem at position i.

The third line contains N integers W₁,W₂,...,W_N , where W_i represents the weight of the gem at position i.

The next Q lines each contain a single integer m, specifying the endpoint for each query.

Constraints

• 1 ≤ N,Q ≤ 10⁵
• 1 ≤ C_i ≤ 7
• 1 ≤ W_i ≤ 10⁵
• 1 ≤ m ≤ N

Subtasks

• Testcases 1~2: N,Q ≤ 10
• Testcases 3~4: N,Q ≤ 10²
• Testcases 5~6: N ≤ 10⁴ , Q = 1
• Testcases 7~8: Q = 1
• Testcases 9~10: No additional restrictions.

Output

For each query, output two integers in a single line:

1. The maximum number of distinct gem colors you can collect up to position m.
2. The maximum total weight of the gems you can collect, with the maximum number of distinct gem colors, up to position m.

Please remember to print "\n" at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss