#1464. JSOI2012 铁拳

JSOI2012 铁拳

Description

经过了可怕的第三次世界大战后,国家政府崩溃,各大财团趁机夺取掌控世界。长年战争后,八大财团幸存并割据一方,其中最强的当属掌控北美的铁拳。

在铁拳财团所维护的文明区域中,有一项最为光荣、重要的赛事——Iron Fist,也就是铁拳大赛。IF中云集了世界各地各财团鼎力资助的世外高手,只为了赢得IF Champion,得到无上的荣耀,当然还有随之而来的权力。本来一切秩序井然,但一个来自贫民窟的少年风间仁意外地在海选中赢了IF正式选手,获得了决赛资格,从此格局被打乱……

为了应对这突如其来的变数,IF管理层决定先对联盟中所有的选手进行评估,以更好地掌握大局。

已知最近m届比赛出现过的n位选手,背后都有着各自财团的资助,并且签下了合同。由于这是各财团的高度机密,合同的具体细节无从得知,但铁拳财团的间谍们通过各种渠道得知了每个选手的薪金范围(显然薪金是非负数)。

对于最近m届的IF比赛(从1开始编号),每一届联盟都会进行清算,通过国际金融手段准确计算出这一届联盟选手身价总和的变化。每一届中,会有一些新选手加入,也会有部分选手在比赛中丧失了战斗能力,而被踢出联盟,流放到贫民窟。

现在给出联盟中n位选手的身价范围,以及他们 进入联盟的届数(0表示在m+1届以前就已经是联盟选手) 和 离开联盟的届数(0表示是现役选手)。同时给出最近m届中,每一届联盟选手身价总和减去上一届的值。

请你根据现有信息,尽可能准确地给出每个选手可能的薪金范围。各选手之间的薪金范围可以不同时成立,但对于一位选手的范围中的每一个数,都必须至少存在一种合法方案使该选手能得到相应薪金,而且这个范围跨度要尽可能大。

如果输入信息有误,请输出-1,表示无解。

Format

Input

第一行一个正整数m,意义见上(下同)。

第二行包含m个整数,第i个表示第i届中 选手身价总和 的变化情况。

第三行一个正整数n。

接下来n行,每行包含四个整数,分别表示 身价下限 、 身价上限 、 出道届数 、 退役届数,细节请参照上文。

保证出道时间严格比退役时间小(0除外)。

Output

如果输入信息有误,仅输出一行一个整数“-1”(不含双引号)。

否则输出n行,每行两个实数,第i行表示第i个选手实际身价的准确范围。

保留两位小数,需要与标准答案完全相同才得分。

Samples

2
5 -1
3
1 4 1 0
2 3 1 0
1 5 1 2
1.00 2.00
2.00 3.00
1.00 1.00

Limitation

第二届只有3号离开了,可以锁定3号的薪金是1。

如此一来,1号和2号薪金之和为4,那么1号最少能拿1,最多能拿2;2号最少能拿到2,最多能拿到3。

对于100%的数据,n≤200,m≤100,给定薪金范围不超过20000。