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。