Longest Contiguous User Activity Sequence

In this problem, you are given an activity log of several users. Each activity is represented by three integers: the user ID, a page ID, and a timestamp. A contiguous page visit sequence for a user is defined as a sequence of activities where the timestamps are consecutive integers, i.e. $t, t+1, \dots, t+k-1$. Your task is to determine, for each test case, the user with the longest contiguous sequence of page visits. In the event of multiple users having the same maximum contiguous sequence length, choose the one with the smallest starting timestamp; if there is still a tie, choose the user with the smallest user ID.

Example: Consider the following input:

2
6
1 10 1
1 11 2
1 12 3
2 13 1
2 14 2
2 15 4
5
3 16 1
3 17 2
3 18 3
4 19 2
4 20 3

The expected output is:

1 1 3
3 1 3

Here, in the first case, user 1 has a contiguous sequence from timestamp 1 to 3 with length 3, which is the longest. In the second case, user 3’s sequence from 1 to 3 is chosen.

inputFormat

The input is given through standard input (stdin). The first line contains an integer $T$ representing the number of test cases. For each test case, the first line contains an integer $N$, the number of activities. This is followed by $N$ lines, each containing three space-separated integers: the user ID, the page ID, and the timestamp.

outputFormat

For each test case, print a single line that contains three space-separated integers: the user ID, the starting timestamp and the ending timestamp of the longest contiguous page visit sequence. The output should be sent to standard output (stdout).## sample

1
6
1 10 1
1 11 2
1 12 3
2 13 1
2 14 2
2 15 4

1 1 3