1760: Sushi

Raven likes eating sushi. One day, a new sushi restaurant is opened near his home, and he goes there to enjoy sushi. After entering the restaurant, he finds out that there are N rotating plates with numbers from 0 to N-1. The sushi maker is in the middle of the rotating plates. Plate facing to the sushi chief is always numbered as 0, and note that the sushi chief doesn’t rotate with the plates. The plates move to the direction of larger numbers, which means that Number 0 moves to the direction of Number 1 and Number 1 moves to the direction of Number 2…… Number N-1 moves to the direction of Number 0. The sushi chef will put the sushi into the rotating plates from time to time. On the other side of the rotating plates, each number faces one seat. There are N seats in total, and numbers of the seats match the number of plates. There are customers in some seats (Of course, every seat is for one customer only). When sushi pass by, the customers will always pick them up from the plates and eat them. In case nobody takes the sushi after a whole round, the sushi chef will take it back to avoid wasting. When customers are about to leave, waiters will greet them and settle the bill. Let’s suppose that the plates are moving so fast that we can neglect the time which it takes for the sushi to arrive at the first customer. When seeing this new sale method, Raven wants to know the sales turnover of the sushi restaurant. He spends one day in the restaurant and records what has happened during the day. Now he hopes that you may help him calculate how much each customer needs to pay before he leaves.

The first line of the input contains an integer T, which indicate the number of test cases. In the next row, there are two positive integers M and N (1 <= M <= 2*10^5, 1 <= N <= 10^5). M means the number of cases which have happened in the sushi restaurant in the one day, and N indicates the number of plates. In the following M rows, each row represents one case, and they are listed according to time. There are three types of cases, including: (1) Customers enter the sushi restaurant; (2) Customers leave the restaurant; (3) Sushi chef put sushi into the rotating plates. Every case is represented by a few numbers. The first number represents the type of the case (1, 2 & 3 represent the above mentioned three cases). If the case belongs to the first type, then there will be two more numbers, a and b, which means customer a is sitting on seat b. The input should make sure that every customer has a unique number and that b is an empty seat. For case 2, there is only one more number, a, which means customer a is leaving. The input should make sure that customer is existence. For case 3, there are two more numbers, a and b, which means that sushi chef put a sushi with a price of a into plate labeled b.

For each case of event 2, output the amount of payment of a customer (the price value of the sushi he has eaten). After every group of data, output a line made up by ten ‘*‘.

3
9 7
1 15 0
1 1 2
1 13 4
3 1 0
3 10 6
3 100 1
2 1
2 13
2 15
9 7
1 15 0
1 1 2
1 13 4
3 1 0
3 10 6
2 1
3 100 1
2 13
2 15
9 7
1 15 0
2 15
3 1 0
3 10 6
3 100 1
1 1 2
1 13 4
2 13
2 1

100
0
11
**********
0
100
11
**********
0
0
0
**********

Sample 1: Customer 15 has sushi priced at 1 and 10, and Customer 1 has sushi priced at 100. Sample 2: Customer 1 leaves the restaurant before the sushi priced at 100 appears, then Customer 13 takes that sushi. Sample 3: All the sushi are taken back by the chef, and no one has had anything.