Description

After narrowly escaping the second trial, you step into the third and final part of the Magical Corridor. The air feels heavier, and the shimmering walls seem to mock your every step.

This time, the corridor presents a new challenge: not only must you gather gems as before, but now you must also deal with the mysterious shopkeepers stationed along the path.

In this corridor, every position contains either a gem or a shop:

• Gems: You can collect them as usual when you pass by.
• Shops: You can trade any one gem you already have for a new one. The shopkeeper will give you one gem of any color you choose, with a weight of W_i ​. However, the shopkeepers are very evil: the weight W_i​ of the gems you get from shops will always be smaller than the weight of the gems you can collect directly (see Constraints for details).

Thanks to your clever mind, you already know exactly where every gem and shop is in the corridor. With this knowledge, you must plan your path carefully.

Your ultimate goal remains the same:

• For a given position m, collect the maximum number of different gem colors.
• If there are multiple ways to collect the most 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 outsmart this new challenge and finally escape?

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​ is:

• 0 : A shop is at position i.
• 1 ≤ C_i ​≤ 7 : A gem of color C_i​ is at position i.

The third line contains N integers W₁​,W₂​,…,W_N​, where W_i​ is:

• The weight of the gem at position i (if C_i ≠ 0).
• The weight of the gems offered by the shop at position i (if C_i = 0).

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

Constraints

• 1 ≤ N ≤ 3 × 10⁴
• 1 ≤ Q ≤ 10⁵
• 0 ≤ C_i ≤ 7
• if C_i = 0, 1 ≤ W_i ≤ 99
• if C_i ≠ 0, 100 ≤ W_i ≤ 10⁵
• 1 ≤ m ≤ N

Subtasks

• Testcases 1~3: 1 ≤ C_i ≤ 7
• Testcases 4~5: 
  • 1 ≤ C_i ≤ 7 for all i ≤ N / 2 
    (In other words, the shops can only appear in the second half of the corridor, and can only be the endpoint of each query.)
  • if C_i ≠ 0, W_i = 100 (the weights of all gems are the same).
  • It is guaranteed that for each query, making at most a single trade will result in the optimal solution.
• Testcases 6~7: 
  • 1 ≤ C_i ≤ 7 for all i ≤ N / 2
    (In other words, the shops can only appear in the second half of the corridor, and can only be the endpoint  of each query.)
  • if C_i ≠ 0, W_i = 100 (the weights of all gems are the same).
• Testcases 8~9:  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