1445 . ඞ
TopCoder
Tags
Description
There is an imposter among us!
你和你的 $N$ 個朋友們正在玩鬼抓人遊戲，這次輪到你當鬼了，除了你自己以外其他人都不知道你是鬼，而你的目標是到遊戲結束前都不被其他人發現身份。根據你多年的遊戲經驗，你知道其他 $N$ 個玩家中的第 $i$ 個將會在一個連續的時間區間裡面跟你待在同一間房間，而且這個時間區間只有可能是兩種可能之一：遊戲開始後 $a_i$ 分鐘到開始後 $b_i$ 分鐘、或者是 $c_i$ 分鐘到 $d_i$ 分鐘。
只要所有人和你都同時待在同一間房間，你的身份暴露的風險就會大大提高。現在你想知道，你和所有人同時在同一間房間的時間至少會是幾分鐘？
Input Format
輸入第一行有一個整數 $T$，代表接下來有 $T$ 筆測試，分別代表一局遊戲。
每一筆測試的第一行有一個整數 $N$，代表這局遊戲除了你之外有幾個人參加；接下來的 $N$ 行每行四個整數 $a_i, b_i, c_i, d_i$ 代表第 $i$ 個人和你待在同一個房間的時間區間。
- $T, N > 0$
- $\sum N \leq 10^ 6$
- $0 \leq a_i, b_i, c_i, d_i \leq 10^ 9$
- $a_i \leq b_i$, $c_i \leq d_i$
Output Format
對於每一筆測試，輸出一行一個整數，代表你至少會有幾分鐘和所有人同時一起待在同一間房間裡面。
Sample Input 1
2 2 1 3 3 5 2 4 2 4 2 1 3 3 5 1 3 3 5
Sample Output 1
1 0
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資。 | 0 |
| 2 | 0~15 | 無特別限制。 | 100 |