CDC12_I - Innovative Combination

no tags 

Suddenly Ronny opened his eyes, the entire battle was only a dream! Then he looked up his watch and realize that it was really late, and decided to go back home.

Immediately after his arrival he received a call from CEIDEC (Center of Extraordinary Investigations Defining Excluded Creatures), they needed a password to open the exit door of the congress, and Ronny was the only one that knew the combination, but he forgot it! Fortunately, he had a "clue" of the password that says: Given a sequence of numbers, and a special list of numbers, the password would be the number of appearance of each special number on the first sequence, keeping the order of the list of special numbers.

Input

The first line contains an integer T, which specifies the number of test cases. Then, will follow the descriptions of T test cases.

Each test case description will contain an integer N and an integer M. N is the size of the first sequence of numbers, and M is the size of the list of special numbers. Note: A special number will not always appear at least once on the entire sequence.

After that, a line with N numbers that represents the sequence, and then a line with M numbers that represents the list of special numbers. The input must be read from standard input.

Output

For each input case you must print a single line with the string "Scenario #i: " where i is the number of the test case (starting at 1), followed by the password of the exit door of the congress. The output must be written to standard output.

Example

Input:
3
5 2
3 3 5 4 4
5 4
7 4
4 8 5 5 5 4 8
4 4 8 5
10 6
3 3 7 6 5 5 7 6 6 6
5 7 6 6 3 5

Output:
Scenario #1: 12
Scenario #2: 2223
Scenario #3: 224422

Constraints

  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 100,000
  • 1 ≤ M ≤ 100,000
  • 1 ≤ Ni, Mi ≤ 100,000

hide comments
satoruu: 2016-04-26 14:04:03

Nice problem for learning STL. AC on the first try :)

:D: 2012-11-28 07:17:30

It's not trivial by principle, but easy. But despite the high constraints, it can be AC'ed with very rough use std::map and scanf. Moving to tutorial.

Some solution here could be having data generated with a formula, like in LCPC12C. It would also be better to have bigger constrains on arrays values (<= 10^9).

Last edit: 2012-11-28 07:19:32

Added by:Venezuelan Programming League
Date:2012-10-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for UCV-CEIDEC contest.