MNNNITPA - Party trouble

no tags 

Chintamani is throwing a party tonight (YAY!!! :)) But there is a slight problem. He ordered a packet of toffees. Fussy he is, he had given strict orders to the shopkeeper that in the packet all toffees should be of different kind. That is no more than one toffee of each variety should be there.

Each type of toffee has a unique identification number written on it. He has received the packet from the shopkeeper but he wants to check the same. He starts taking out toffee from the packet one by one saying the id number of the toffee.

Help him in this task by telling him whether a toffee with the id number he just said has occurred before or not.

Input

The first line of the input will be the number of test cases (T <= 10). For each test case first line contains one integer n denoting the number of toffees in the packet 0 <= n <= 10^6. n lines follow each containing the id number for a toffee. 0 <= id <= 10^9.

Output

You have to output total n lines for each test case. For each input if the toffee with the given id has already occurred output "DUPLICATE" else output "OK".

Example

Input:
2
4
7
5
1
5
3
2
2
1

Output:
OK
OK
OK
DUPLICATE
OK
DUPLICATE
OK

hide comments
UJtriumphsâ„¢: 2014-10-03 20:36:11

getting wrong answer working fine in ideone can u provide any tricky test case my submission id #12535022

Francky: 2012-08-11 13:00:44

Should be move to tutorial. Do not remove this comment ! :-(

(Tjandra Satria Gunawan)(曾毅昆): 2012-08-11 09:04:22

Seems that the test data is not optimal (n is relative small) because there's no effect if you use Fast I/O or not.

ken_taiken: 2012-08-11 09:04:19

It's quite easy and straight-forward. Kinda like a tutorial for mapping.

(Tjandra Satria Gunawan)(曾毅昆): 2012-08-11 08:32:34

@anonymous: it's possible to work with C program :) but require a lot of memory.

!@#$ : 2012-08-11 05:00:53

seems impossible in c,but time limit is less for other languages :(:(


Added by:bashrc is back
Date:2012-08-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64