Description

The wicked sorcerer KenKenKen is hot on your trail, casting spells to trap you. To escape his grasp, you must navigate the mysterious Magical Corridor.

This corridor has N positions, numbered from 1 to N, each holding a gem with a color C_i​ and a weight W_i​.

To escape, you must collect gems along the way, but your movement is restricted by magical rules:

• If you are currently 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,…

The only way to open the magical exit and escape the corridor is to meet the following condition:

• For a given position m, collect as many distinct gem colors as possible.
• Among all collections with the maximum number of distinct colors, maximize the total weight of the gems you collect.
• However, because KenKenKen 's cursed, your bag can only hold one gem of each color, you are limited to carrying at most one gem of each color.

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 ≤ 10⁴ , C_i = 1
• Testcases 5~6: N ≤ 10⁴ , W_i = 1
• Testcases 7~8: N ≤ 10⁴ , 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