안도라
시간 제한2초메모리 제한512 MB
투자자를 순서대로 처리하면서, 해당 타입의 남은 블록을 하나 이상 포함하는 연속 구간의 수를 세고, 그 타입의 남은 블록을 모두 제거한 뒤 남는 전체 구간의 수를 구한다.
문제
안도라는 여러 개의 블록이 나란히 늘어선 가로로 긴 도시다. 각 블록은 그 종류를 나타내는 번호를 가지며, 여러 블록이 같은 종류를 가질 수 있다.
Andy는 안도라의 시공업자다. 경험상 Andy는 투자자를 만날 때 그 투자자가 어떤 종류의 블록을 사고 싶어 하는지 대개 알고 있다. 관심 있는 종류만 보여 주면 너무 뻔해서 투자자가 가격을 깎으려 할 수 있다.
머리가 좋은 Andy는 투자자에게 투어를 하나 보여 준다. 투어는 블록 하나일 수도 있고 연속한 여러 블록일 수도 있으며, 투자자가 원하는 종류의 블록을 적어도 하나 포함해야 한다. 투어가 끝나면 Andy는 그 종류의 블록을 모두 투자자에게 판다. 이미 팔린 블록은 투어에 넣을 수 없다. 그러면 주인이 화를 내기 때문이다.
Andy에게는 여러 투자자가 차례로 찾아오고, Andy는 도착한 순서대로 이들을 상대한다. Andy는 계획을 세우는 데 당신의 도움이 필요하다. 각 투자자마다 Andy는 다음을 알고 싶어 한다.
- 그 투자자에게 보여 줄 수 있는 투어는 몇 개인가.
- 그 투자자를 상대하고 난 뒤에 남아 있는 투어는 몇 개인가. (투어에는 이미 팔린 블록이 들어갈 수 없다.)
입력
입력은 하나 이상의 테스트 케이스로 이루어진다. 입력의 첫 줄에는 정수 T (1 ≤ T ≤ 100)가 주어진다.
각 테스트 케이스의 첫 줄에는 공백으로 구분된 두 정수가 주어진다.
- N: 도시에 있는 블록의 수 (0 ≤ N ≤ 100,000)
- Q: 투자자의 수 (1 ≤ Q ≤ 100,000)
이어서 두 줄이 주어진다. 첫 번째 줄에는 공백으로 구분된 N개의 정수가 주어지며, 각 정수 x는 i번째 블록의 종류를 나타낸다. 두 번째 줄에는 공백으로 구분된 Q개의 정수가 주어지며, 각 정수 y는 j번째 투자자가 관심을 가지는 블록의 종류를 나타낸다. (1 ≤ x, y ≤ 1,000,000,000)
출력
각 테스트 케이스마다 Q개의 줄을 출력한다. 각 줄에는 공백으로 구분된 두 정수를 출력한다. j번째 줄에는 j번째 투자자에게 가능한 투어의 수와 그 투자자를 상대하고 난 뒤에 가능한 투어의 수를 순서대로 출력한다.
힌트
참고: 예제에서 안도라에는 블록이 2개 있다. 처음에는 모두 팔리지 않았으므로 Andy는 3개의 투어를 보여 줄 수 있다.
- 1번 블록에서 1번 블록까지 (1,1)
- 1번 블록에서 2번 블록까지 (1,2)
- 2번 블록에서 2번 블록까지 (2,2)
- 종류 1의 블록에 관심이 있는 투자자가 온다. Andy는 그에게 두 개의 투어 (1,1)과 (1,2)를 보여 줄 수 있다. 1번 블록을 팔고 나면 더 이상 쓸 수 없으므로 Andy는 이제 투어 (2,2)만 보여 줄 수 있다. 따라서 답은 '2 1'이다.
- 종류 2의 블록에 관심이 있는 투자자가 온다. Andy는 그에게 투어 (2,2) 하나만 보여 줄 수 있다. 팔고 나면 모든 블록이 팔렸으므로 더 이상 투어가 불가능하다. 따라서 답은 '1 0'이다.