시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1553 625 500 42.553%

문제

당신은 유명 프로그래밍 대회인 KCPC(Korean Collegiate Programming Contest)에 참가하고 있다. 이 대회에서 총 k개의 문제를 풀게 되는데, 어떤 문제에 대한 풀이를 서버에 제출하면 그 문제에 대해 0점에서 100점 사이의 점수를 얻는다. 풀이를 제출한 팀의 ID, 문제 번호, 점수가 서버의 로그에 제출되는 시간 순서대로 저장된다. 한 문제에 대한 풀이를 여러 번 제출할 수 있는데, 그 중 최고 점수가 그 문제에 대한 최종 점수가 된다. (만약 어떤 문제에 대해 풀이를 한번도 제출하지 않았으면 그 문제에 대한 최종 점수는 0점이다.) 

당신 팀의 최종 점수는 각 문제에 대해 받은 점수의 총합이고, 당신의 순위는 (당신 팀보다 높은 점수를 받은 팀의 수)+1 이다. 

점수가 동일한 팀이 여럿 있을 수 있는데, 그 경우에는 다음 규칙에 의해서 순위가 정해진다. 

  1. 최종 점수가 같은 경우, 풀이를 제출한 횟수가 적은 팀의 순위가 높다. 
  2. 최종 점수도 같고 제출 횟수도 같은 경우, 마지막 제출 시간이 더 빠른 팀의 순위가 높다. 

동시에 제출되는 풀이는 없고, 모든 팀이 적어도 한 번은 풀이를 제출한다고 가정하라. 

서버의 로그가 주어졌을 때, 당신 팀의 순위를 계산하는 프로그램을 작성하시오.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 팀의 개수 n, 문제의 개수 k, 당신 팀의 ID t, 로그 엔트리의 개수 m을 나타내는 4 개의 정수가 주어진다. 여기서, 3 ≤ n, k ≤ 100, 1 ≤ t ≤ n, 3 ≤ m ≤ 10,000이다. 그 다음 m개의 줄에는 각 풀이에 대한 정보가 제출되는 순서대로 주어진다. 각 줄에는 팀 ID i, 문제 번호 j, 획득한 점수 s를 나타내는 세 개의 정수가 주어진다. 여기서 1 ≤ i ≤ n, 1 ≤ j ≤ k, 0 ≤ s ≤ 100이다. 

출력

출력은 표준출력을 사용한다. 주어진 각 테스트 데이터에 대해 당신 팀의 순위를 한 줄에 출력하여야 한다

예제 입력 1

2
3 4 3 5
1 1 30
2 3 30
1 2 40
1 2 20
3 1 70
4 4 1 10
1 1 50
2 1 20
1 1 80
3 1 0
1 2 20
2 2 10
4 3 0
2 1 0
2 2 100
1 4 20

예제 출력 1

1
2
W3sicHJvYmxlbV9pZCI6IjM3NTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJLQ1BDIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZjlcdWMyZTBcdWM3NDAgXHVjNzIwXHViYTg1IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmMwZCBcdWIzMDBcdWQ2OGNcdWM3NzggS0NQQyhLb3JlYW4gQ29sbGVnaWF0ZSBQcm9ncmFtbWluZyBDb250ZXN0KVx1YzVkMCBcdWNjMzhcdWFjMDBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViMzAwXHVkNjhjXHVjNWQwXHVjMTFjIFx1Y2QxZCBrXHVhYzFjXHVjNzU4IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0ODBcdWFjOGMgXHViNDE4XHViMjk0XHViMzcwLCBcdWM1YjRcdWI1YTQgXHViYjM4XHVjODFjXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWQ0ODBcdWM3NzRcdWI5N2MgXHVjMTFjXHViYzg0XHVjNWQwIFx1YzgxY1x1Y2Q5Y1x1ZDU1OFx1YmE3NCBcdWFkZjggXHViYjM4XHVjODFjXHVjNWQwIFx1YjMwMFx1ZDU3NCAwXHVjODEwXHVjNWQwXHVjMTFjIDEwMFx1YzgxMCBcdWMwYWNcdWM3NzRcdWM3NTggXHVjODEwXHVjMjE4XHViOTdjIFx1YzViYlx1YjI5NFx1YjJlNC4gXHVkNDgwXHVjNzc0XHViOTdjIFx1YzgxY1x1Y2Q5Y1x1ZDU1YyBcdWQzMDBcdWM3NTggSUQsIFx1YmIzOFx1YzgxYyBcdWJjODhcdWQ2MzgsIFx1YzgxMFx1YzIxOFx1YWMwMCBcdWMxMWNcdWJjODRcdWM3NTggXHViODVjXHVhZGY4XHVjNWQwIFx1YzgxY1x1Y2Q5Y1x1YjQxOFx1YjI5NCBcdWMyZGNcdWFjMDQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzgwMFx1YzdhNVx1YjQxY1x1YjJlNC4gXHVkNTVjIFx1YmIzOFx1YzgxY1x1YzVkMCBcdWIzMDBcdWQ1NWMgXHVkNDgwXHVjNzc0XHViOTdjIFx1YzVlY1x1YjdlYyBcdWJjODggXHVjODFjXHVjZDljXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YWRmOCBcdWM5MTEgXHVjZDVjXHVhY2UwIFx1YzgxMFx1YzIxOFx1YWMwMCBcdWFkZjggXHViYjM4XHVjODFjXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWNkNWNcdWM4ODUgXHVjODEwXHVjMjE4XHVhYzAwIFx1YjQxY1x1YjJlNC4gKFx1YjljY1x1YzU3ZCBcdWM1YjRcdWI1YTQgXHViYjM4XHVjODFjXHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWQ0ODBcdWM3NzRcdWI5N2MgXHVkNTVjXHViYzg4XHViM2M0IFx1YzgxY1x1Y2Q5Y1x1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NThcdWM3M2NcdWJhNzQgXHVhZGY4IFx1YmIzOFx1YzgxY1x1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjZDVjXHVjODg1IFx1YzgxMFx1YzIxOFx1YjI5NCAwXHVjODEwXHVjNzc0XHViMmU0LikmbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjMmUwIFx1ZDMwMFx1Yzc1OCBcdWNkNWNcdWM4ODUgXHVjODEwXHVjMjE4XHViMjk0IFx1YWMwMSBcdWJiMzhcdWM4MWNcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YmMxYlx1Yzc0MCBcdWM4MTBcdWMyMThcdWM3NTggXHVjZDFkXHVkNTY5XHVjNzc0XHVhY2UwLCBcdWIyZjlcdWMyZTBcdWM3NTggXHVjMjFjXHVjNzA0XHViMjk0IChcdWIyZjlcdWMyZTAgXHVkMzAwXHViY2Y0XHViMmU0IFx1YjE5Mlx1Yzc0MCBcdWM4MTBcdWMyMThcdWI5N2MgXHViYzFiXHVjNzQwIFx1ZDMwMFx1Yzc1OCBcdWMyMTgpKzEgXHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM4MTBcdWMyMThcdWFjMDAgXHViM2Q5XHVjNzdjXHVkNTVjIFx1ZDMwMFx1Yzc3NCBcdWM1ZWNcdWI3ZmYgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YWRmOCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViMmU0XHVjNzRjIFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWM3NThcdWQ1NzRcdWMxMWMgXHVjMjFjXHVjNzA0XHVhYzAwIFx1YzgxNVx1ZDU3NFx1YzljNFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWNkNWNcdWM4ODUgXHVjODEwXHVjMjE4XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjAsIFx1ZDQ4MFx1Yzc3NFx1Yjk3YyBcdWM4MWNcdWNkOWNcdWQ1NWMgXHVkNjlmXHVjMjE4XHVhYzAwIFx1YzgwMVx1Yzc0MCBcdWQzMDBcdWM3NTggXHVjMjFjXHVjNzA0XHVhYzAwIFx1YjE5Mlx1YjJlNC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+XHVjZDVjXHVjODg1IFx1YzgxMFx1YzIxOFx1YjNjNCBcdWFjMTlcdWFjZTAgXHVjODFjXHVjZDljIFx1ZDY5Zlx1YzIxOFx1YjNjNCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwLCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjODFjXHVjZDljIFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWIzNTQgXHViZTYwXHViOTc4IFx1ZDMwMFx1Yzc1OCBcdWMyMWNcdWM3MDRcdWFjMDAgXHViMTkyXHViMmU0LiZuYnNwOzxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YjNkOVx1YzJkY1x1YzVkMCBcdWM4MWNcdWNkOWNcdWI0MThcdWIyOTQgXHVkNDgwXHVjNzc0XHViMjk0IFx1YzVjNlx1YWNlMCwgXHViYWE4XHViNGUwIFx1ZDMwMFx1Yzc3NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjIFx1YmM4OFx1Yzc0MCBcdWQ0ODBcdWM3NzRcdWI5N2MgXHVjODFjXHVjZDljXHVkNTVjXHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1OFx1Yjc3Yy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjMTFjXHViYzg0XHVjNzU4IFx1Yjg1Y1x1YWRmOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWIyZjlcdWMyZTAgXHVkMzAwXHVjNzU4IFx1YzIxY1x1YzcwNFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNSBcdWIzNzBcdWM3NzRcdWQxMzBcdWIyOTQgXHVkNDVjXHVjOTAwIFx1Yzc4NVx1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc0MCBUXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWIzNzBcdWM3NzRcdWQxMzBcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMzAwXHVjNzU4IFx1YWMxY1x1YzIxOCBuLCBcdWJiMzhcdWM4MWNcdWM3NTggXHVhYzFjXHVjMjE4IGssIFx1YjJmOVx1YzJlMCBcdWQzMDBcdWM3NTggSUQgdCwgXHViODVjXHVhZGY4IFx1YzVkNFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMTggbVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgNCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjLCAzICZsZTsgbiwgayAmbGU7IDEwMCwgMSAmbGU7IHQgJmxlOyBuLCAzICZsZTsgbSAmbGU7IDEwLDAwMFx1Yzc3NFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVkNDgwXHVjNzc0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjODFjXHVjZDljXHViNDE4XHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMzAwIElEIGksIFx1YmIzOFx1YzgxYyBcdWJjODhcdWQ2MzggaiwgXHVkNjhkXHViNGRkXHVkNTVjIFx1YzgxMFx1YzIxOCBzXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzVlY1x1YWUzMFx1YzExYyAxICZsZTsgaSAmbGU7IG4sIDEgJmxlOyBqICZsZTsgaywgMCAmbGU7IHMgJmxlOyAxMDBcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1ZDQ1Y1x1YzkwMFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1YzhmY1x1YzViNFx1YzljNCBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHViMmY5XHVjMmUwIFx1ZDMwMFx1Yzc1OCBcdWMyMWNcdWM3MDRcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NThcdWM1ZWNcdWM1N2MgXHVkNTVjXHViMmU0PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzc1OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktDUEMiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgcGFydGljaXBhdGluZyBpbiB0aGUgcHJlc3RpZ2lvdXMgcHJvZ3JhbW1pbmcgY29tcGV0aXRpb24gY2FsbGVkIEtDUEMgKEtvcmVhbiBDb2xsZWdpYXRlIFByb2dyYW1taW5nIENvbnRlc3QpLiBZb3UgYXJlIHN1cHBvc2VkIHRvIHNvbHZlIGsgcHJvYmxlbXMgYW5kIGZvciBlYWNoIHByb2JsZW0geW91IGdldCBiZXR3ZWVuIDAgYW5kIDEwMCBwb2ludHMgZWFjaCB0aW1lIHlvdSBzdWJtaXQgeW91ciBzb2x1dGlvbiB0byB0aGUgc2VydmVyLiBUaGUgc3VibWlzc2lvbiBpcyBkb25lIGVsZWN0cm9uaWNhbGx5IGFuZCB0aGUgc2VydmVyIG1haW50YWlucyBhIGxvZyBpbiBvcmRlciBvZiBzdWJtaXNzaW9uIHRpbWUuIFRoZSBsb2cgaW5jbHVkZXMgeW91ciB0ZWFtIElELCB0aGUgcHJvYmxlbSBudW1iZXIsIGFuZCB5b3VyIHNjb3JlLiBGb3IgYW55IHByb2JsZW0geW91IGNhbiBzdWJtaXQgeW91ciBzb2x1dGlvbiBzZXZlcmFsIHRpbWVzIGFuZCB5b3UgZ2V0IHRoZSBncmVhdGVzdCBwb2ludHMgYW1vbmcgeW91ciBzdWJtaXNzaW9ucy4gKEZvciBhIHByb2JsZW0sIHlvdSBnZXQgMCBwb2ludHMgaWYgeW91IG1ha2Ugbm8gc3VibWlzc2lvbiBmb3IgdGhlIHByb2JsZW0uKSZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3VyIGZpbmFsIHNjb3JlIGlzIHNpbXBseSB0aGUgc3VtIG9mIHRoZSBwb2ludHMgeW91IGVhcm5lZCBhbmQgeW91ciByYW5raW5nIGlzICh0aGUgbnVtYmVyIG9mIHRlYW1zIHdpdGggaGlnaGVyIHNjb3JlIHRoYW4geW91cnMpICsgMS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SG93ZXZlciwgdGhlcmUgbWF5IGJlIHR3byBvciBtb3JlIHRlYW1zIHdpdGggdGhlIHNhbWUgc2NvcmUgYW5kIHRoZSB0aWUgaXMgYnJva2VuIGJ5IGFwcGx5aW5nIHRoZSBncm91bmQgcnVsZXMgaW4gdGhlIGZvbGxvd2luZyBvcmRlci4mbmJzcDs8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5JZiB0aGUgZmluYWwgc2NvcmVzIGFyZSB0aGUgc2FtZSwgdGhlIHRlYW0gd2l0aCB0aGUgc21hbGxlciBudW1iZXIgb2Ygc3VibWlzc2lvbnMgaW4gdG90YWwgd2lucy4mbmJzcDs8XC9saT5cclxuXHQ8bGk+SWYgYm90aCB0aGUgZmluYWwgc2NvcmVzIGFuZCB0aGUgbnVtYmVycyBvZiBzdWJtaXNzaW9uIGFyZSB0aGUgc2FtZSwgdGhlIHRlYW0gd2hvc2UgbGFzdCBzdWJtaXNzaW9uIGlzIGVhcmxpZXIgd2lucy4mbmJzcDs8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Bc3N1bWUgdGhhdCBubyB0d28gc29sdXRpb25zIGFyZSBzdWJtaXR0ZWQgYXQgdGhlIHNhbWUgdGltZSBhbmQgZXZlcnkgdGVhbSBtYWtlcyBhdCBsZWFzdCBvbmUgc3VibWlzc2lvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIGxvZyBvZiB0aGUgc2VydmVyLCB3cml0ZSBhIHByb2dyYW0gdG8gY29tcHV0ZSB5b3VyIHJhbmtpbmcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGZvdXIgaW50ZWdlcnMsIHRoZSBudW1iZXIgb2YgdGVhbXMgbiwgdGhlIG51bWJlciBvZiBwcm9ibGVtcyBrLCB5b3VyIHRlYW0gSUQgdCwgYW5kIHRoZSBudW1iZXIgb2YgbG9nIGVudHJpZXMgbSwgd2hlcmUgMyAmbGU7IG4sayAmbGU7IDEwMCwgMSAmbGU7IHQgJmxlOyBuLCBhbmQgMyAmbGU7IG0gJmxlOyAxMCwwMDAuIEluIHRoZSBmb2xsb3dpbmcgbSBsaW5lcywgdGhlIGluZm9ybWF0aW9uIG9uIHN1Ym1pc3Npb24gaXMgZ2l2ZW4gaW4gb3JkZXIgb2Ygc3VibWlzc2lvbiB0aW1lLiBFYWNoIGxpbmUgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMsIHRlYW0gSUQgaSwgcHJvYmxlbSBudW1iZXIgaiwgYW5kIHNjb3JlIHMsIHdoZXJlIDEgJmxlOyBpICZsZTsgbiwgMSAmbGU7IGogJmxlOyBrLCBhbmQgMCAmbGU7IHMgJmxlOyAxMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIHlvdXIgcmFua2luZy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=