Wayne喜欢玩游戏，并且时常在游戏中思考怎么玩儿才能使花的时间最少。

  某天Wayne在玩儿一个最新的游戏，这个游戏类似于走迷宫：游戏设置在一个二维坐标系中，有一个简单多边形，每条边都平行于某一条坐标轴，且顶点坐标都是整数。游戏中有很多轮，每一轮都会给出位于多边形内的起点S和终点T，Wayne每次从S点出发，每一步可以选择上下左右四个方向之一，前进任意距离，但不能走出多边形。

  因为游戏时间与距离是成正比的，于是Wayne就想知道，每一轮所需要走的最短距离。

  第一行一个正整数N，表示多边形的点数。

  接下来N行按顺时针或逆时针描述这个多边形，每行两个整数XY，表示多边形上点的坐标。

  接下来一行一个正整数M，表示游戏的轮数。

  接下来M行每行四个整数表示起点和终点的坐标，即XsYsXtYt。

  对于每一轮游戏单独输出一行一个非负整数表示所需走的最短距离。

  另外有20%的数据，满足N <= 300，M <= 50。

  另外有25%的数据，满足N <= 10^5，M <= 300。