A - Imosuke Researcher

ストーリー

かつていもす王国という国があった．
いもす家が代々王を務め，国を治めていた．
いもす王国は $1$ 年 $1$ 月 $1$ 日に建国され $100000$ 年 $12$ 月 $31$ 日にその長い歴史に幕を閉じた．
いもす王国の国民は，人生で $1$ 度いもす家に仕えることが義務付けられていた．
偶然にもいもす王国の国民全員の情報が残っていたので，いもす家の末裔である芋助くんはいもす王国の国民のうち，王家に仕えていた人の割合が知りたくなった．

問題文

$N$ 人のいもす王国の国民の情報が与えられます．
国民 $i$ は $A_i$ 年 $1$ 月 $1$ 日に生まれ，$B_i$ 年 $12$ 月 $31$ 日に亡くなりました．
また国民 $i$ は $C_i$ 年 $1$ 月 $1$ 日から $D_i$ 年 $12$ 月 $31$ 日までいもす家に仕えていました．
つまり，国民 $i$ は $A_i$年から $B_i$ 年まで生存しており，$C_i$ 年から $D_i$ 年までいもす家に仕えているということです．
$1$ 年から $100000$ 年までの各年について，その年のいもす王国の人口に対するいもす家に仕えている人の比率を既約分数 $\frac{p}{q}$ で表したとき，p q を出力するプログラムを作成してください．
ただし，ある年の人口とはその年に生存している人数の事を指し，与えられた $N$ 人以外の国民はいないものとします．
また，人口が $0$ 人のときはかわりに -1 と出力してください．
そうでなく，仕えている人が $0$ 人の時は 0 1 と出力してください．

制約

• 入力はすべて整数
• $1 \leq N \leq 2 \cdot 10^5$
• $1 \leq A_i \leq C_i \leq D_i \leq B_i \leq 10^5$

入力

入力は以下の形式で標準入力から与えられる．

$N$

$A_1~B_1~C_1~D_1$

$A_2~B_2~C_2~D_2$

$...$

$A_N~B_N~C_N~D_N$

出力

$10^5$ 行出力せよ．$i$ 行目には $i$ 年のいもす王国の人口に対するいもす家に仕えている人の比率を問題文に示した形式で出力せよ．
ただし，いもす王国の人口が $0$ 人のとき，かわりに -1 と出力せよ．

入力例1

6
1 10 2 5
1 10 1 9
2 10 3 4
1 1 1 1
7 8 8 8
3 9 4 8
Copy

出力例1

2 3
2 3
3 4
1 1
3 4
1 2
2 5
3 5
1 4
0 1
Copy

行数を圧迫するため，はじめの $10$ 行のみを記述してあります．
この例では，残りの $99990$ 行には -1 と出力すればよいです．