問題文

Splarraay ｽﾌﾟﾗﾚｪｰｲは配列を塗りつぶすだけの簡単なゲームです。
プレイヤーはチームAとチームBに分かれ、それぞれのチームを表す色で1つの配列を塗りつぶし合います。
最終的なスコアはそのチームの色で塗りつぶされた要素の数と、後述するボーナスポイントの和で決まり、スコアが高いチームがゲームの勝者となります。

ルール

1. 長さ$N$の、何色にも塗られていない配列が与えられる
2. 2つのチームは配列のある区間$[l,r]$をそのチームの色で塗りつぶしていく。塗りつぶそうとした場所に既に色が塗られていた場合、後から塗られた色で上書きされる
3. 不定期にボーナスチャンスが与えらる。ボーナスチャンスでは区間$[l,r]$が与えられ、その時点でチームAによって塗られている区間$[l,r]$の要素の数を$A_{l,r}$ 、チームBによって塗られている区間$[l,r]$の要素の数を $B_{l,r}$ としたとき、この値が大きい方のチームに $max(A_{l,r}, B_{l,r})$ のボーナスポイントが与えられる。 $A_{l,r}$ と $B_{l,r}$ が等しい場合、どちらにもボーナスポイントは与えられない
4. 時間制限が訪れゲームが終了したとき、配列の全区間$[0,N-1]$の、そのチームの色で塗られている要素の数と、それまでに得たボーナスポイントの和がそのチームのスコアとなる

既にゲームは終了し、後はスコアを計算するだけです。各チームの行動の履歴とボーナスチャンスの詳細が時系列順に与えられるので、最終スコアを算出してください。

入力

$N$
$Q$
$x$ $l$ $r$

$N$ 塗りつぶし合う配列の長さ
$Q$ 各チームの行動の回数とボーナスチャンスの回数の和。以下Q行に渡って行動/ボーナスチャンスの詳細が時系列順に与えられる
$x=0$ のとき、区間$[l,r]$のボーナスチャンス
$x=1$ のとき、チームAによる区間$[l,r]$への塗りつぶし行動
$x=2$ のとき、チームBによる区間$[l,r]$への塗りつぶし行動

また入力は全て整数で与えられ、以下の制約を満たす
$1\leq N \leq 100,000$
$1\leq Q \leq 100,000$
$0\leq x \leq 2$
$0\leq l \leq r \leq N-1$

出力

チームAのスコアとチームBのスコアを空白区切りで出力してください。最後に改行してください。

チームAのスコア チームBのスコア

サンプル

5
2
1 0 3
2 2 4

2 3

[-----]
[AAAA-]
[AABBB]

5
3
1 0 4
2 1 3
0 4 4

3 3

[-----]
[AAAAA]
[ABBBA]
[ABBBA] Bonus! A +1

6
6
1 1 2
2 4 5
0 2 4
2 0 3
1 1 5
0 0 5

10 1

[------]
[-AA---]
[-AA-BB]
[-AA-BB] Bonus!
[BBBBBB]
[BAAAAA]
[BAAAAA] Bonus! A +5