Andorra

Andorra is a horizontal city made up of a set of side-by-side blocks. Each block has a number corresponding to its type, and multiple blocks can have the same type.

Andy is the contractor of Andorra. From experience, when Andy meets an investor he usually knows what type of blocks that investor will be interested in buying. Showing the investor only that type would be too obvious and might make the investor negotiate and reduce the price.

Andy, being the smart guy he is, makes a tour for the investor. The tour could be one block or multiple consecutive blocks, and it must contain at least one block of the type the investor wants. After the tour, Andy manages to sell all blocks of that type to the investor. A tour cannot include blocks that have been sold before, otherwise the owners will be upset.

A series of investors is coming Andy's way, and he deals with them in the order of their arrival. He needs your help in planning. For each investor he wants to know:

• How many tours are possible to give to them.
• How many future tours are available after being done with that investor. (Remember, any tour cannot contain a property that was sold.)

Your program will be tested on one or more test cases. The first line of the input contains a single integer T (1 ≤ T ≤ 100).

Each test case starts with a line containing two space-separated integers:

• N: the number of available city blocks (0 ≤ N ≤ 100,000)
• Q: the number of investors (1 ≤ Q ≤ 100,000)

Two lines follow. The first line contains N space-separated integers, where each integer x represents the type of block i. The second line contains Q space-separated integers, where each integer y represents the block type that investor j is interested in. (1 ≤ x, y ≤ 1,000,000,000)

For each test case, print Q lines, each containing 2 space-separated integers. Line j contains the number of tours possible for investor j and the number of future tours possible after being done with that investor, respectively.

Notes: In the test case, Andorra has 2 blocks. In the beginning they are all free, so Andy can give 3 tours:

• From block 1 to block 1 (1,1)
• From block 1 to block 2 (1,2)
• From block 2 to block 2 (2,2)

1. An investor interested in blocks of type 1 arrives. Andy can make him two tours, (1,1) and (1,2). After selling, block 1 is not available anymore, so Andy can now make only the tour (2,2), and the answer is '2 1'.
2. An investor interested in blocks of type 2 arrives. Andy can make him only one tour, (2,2). After selling, no tours are possible since all blocks are sold now, and the answer is '1 0'.