2637: 砍树

小A是小B家的园丁。小B的家里有n棵树，第i棵树的横坐标为i。一天，小B交给小A一个任务，让他降低自己家中的某些树木的高度。这个任务对小A来说十分简单，因为他有一把极其锋利的斧头和一门独门砍树秘籍，能够轻易地砍断任何参天大树。小A的砍树方法有3种，都是沿着一条y=kx+b的直线砍一段区间的树，相同的方法k值相同。只用了一个下午，小A就完成了小B的任务。第二天，小B来视察小A的任务完成情况。小B想知道小A是否真的用心砍树，于是提出了q个询问，每次询问一段区间中最低的树的高度。小A当然是不会记住树木的砍伐情况的，他只知道自己按什么顺序，使用了什么方法，砍了哪个连续区间的树，而且区间都是互不包含的。现在小A想请你帮帮他，回答小B的询问。

第一行三个整数k1，k2，k3表示小A三种砍树方法的斜率值；

第二行一个数n，表示一共有n棵树；

第三行n个数hi，分别表示n棵树的高度；

第四行一个数m，表示小A一共进行了m次操作；

接下来m行，每行四个数L，R，p，b，表示用第p种方法，即用y=kp+b的直线砍[L，R]区间的树；

接下来一行一个数q，表示小B的询问数；

接下来q行，每行两个数L，R，表示询问[L，R]区间中最低的树的高度。

一共q行，每行一个数h表示对应的回答。

1 0 -1
4
10 30 20 1
2
3 4 2 5
1 3 3 10
2
1 2
2 3

8
5