問題
芽兎めう「ベルトコンベアちくわ大食い大会めう！！！！！！」霜月凛「はんこ屋、無謀よ、やめなさい」
山形まり花「大丈夫だよ！絶対、大丈夫だよ！！」
ベルトコンベアがある。そこに左からN個のちくわをのせる。ちくわは何かの力によってその場から動くことはない。
芽兎めう（めうめう）は、このベルトコンベアを左から右へ移動する。移動する際にちくわを全て食べる。
大食い大会といっても、これは少し特殊である。
ちくわiには、「幸福度」なるものが存在する。幸福度はあるパラメータ(a, b)によって定められている。
幸福度rのめうめうが幸福度パラメータ(a, b)のちくわを食べた際のめうめうの「幸福度」は、
『r × a + b』
となる。この大会は、1~Nまでの全てのちくわを食べ終えた際の「幸福度」が最も高い者が優勝するシステムである。
そして、ちくわiは時間をランダムにおいてM回にわたり別の幸福度パラメータを持ったちくわに置き換えられる。
例として、ちくわ2つに(2, 1), (-1, 3)という幸福度パラメータがあるものを取り上げる。
このような流れで大会は行われる。和泉一舞「何か落ちてるわ・・・ 何これ、ちくわの入れ替え表？」
颯爽とイブの元に現れた凛「でかしたわ洋服屋。これではんこ屋を救うわよ」
あなたは凛から「ちくわの入れ替え表」を受け取った。
これには、ちくわの入れ替えのタイミングと場所、そのちくわの幸福度パラメータが記されていた。
最初の段階では、ちくわの幸福度パラメータは全て(1, 0)で、めうめうの幸福度は1である。
つまり、最初の段階でベルトコンベアをめうめうが滑れば、最終的な幸福度は1のままである。
この表を元に、あなたは凛にめうめうの幸福度の最大値を教えて、めうめうを救ってあげよう。
凛「あ、後ついでに最小値も出して頂戴。 ・・・理由？なんとなくよ」
入力
N M p1 a1 b1 ・ ・ ・ ・ ・ ・ ・ ・ ・ pM aM bM
- 1行目にちくわの個数N、ちくわの交換回数Mが与えられる。
- 2~M-1行目に交換するちくわの情報（場所p, パラメータa, パラメータb）が与えられる。
出力
min max
- 1行目にめうめうの幸福度の最小値を、２行目に最大値を出力する。
- 改行を忘れないこと。
制約
- 1≦N≦1012, 0≦M≦100000
- 1≦r≦N, 0≦a, b≦1 (実数を含む)
- 許容誤差は10-6である。
入力例
入力例1
1 1 1 1 0
出力例1
1 1
解説
- 1度ちくわが入れ替えられているが、入れ替え前後でちくわの幸福度パラメータに変化はない。よって幸福度は1である。
入力例2
3 2 2 -1 1 2 1 0.5
出力例2
0 1.5
解説
- 1回目の入れ替え後は、2個目のちくわで「1 x (-1) + 1 = 0」
- 2回目の入れ替え後は、2個目のちくわで「1 × 1 + 0.5 = 1.5」
- よって、最小値0, 最大値1.5となるので、「1.5」と出力する。
入力例3
4 5 1 -0.8 0.5 2 0.72 -0.21 3 1 0.8 4 0.3 0.4142 3 1 0.8
出力例3
-0.426 1
入力例4
10 10 6 0.5674 -1 3 -0.432 0.1235 8 0.92 0 4 -0.673 0.12578 6 0.986 -0.567 1 0.11111 1 10 0.98765 -0.1234 10 0.18543 -0.16532 9 -0.756 0.54849 2 -1 0.74436
出力例4
-1.175043 1
りんりんせんせーたちからのアドバイス
凛「coutの実数精度指定に『cout.precision(整数);』があるわ。これでprintfを使わなくても実数の精度を気にしなくて済むわね。」
めう「元ネタはARC008-D：タコヤキオイシクナールめう」