背景

机房里面的人最爱玩游戏，这句活说的一点也不错，每天都会有人设计出一种新的小游 戏。。。

问题描述

WZOI的 LZYP 大牛设计出一款小游戏。这个游戏地图是一个 N 行N 列的棋盘组成的（每一个小格都是 1×1 正方形），如图

是一个 5×5 的的地图。LZYP 手中有一枚正方体，这枚正方体的棱长恰好为 1。也就是说，这枚这正方体恰好可以覆盖一个棋盘格子。在正方体的每一个面上分别标上了一个非负整数 W，当然正方体的六个面上的数字不一定相同。现在将这枚正方体放在棋盘上（恰好覆一个格子），一个人可以你在棋盘上滚动该立方体（立方体可以向其前、后、左、右四个方向滚动）。在滚动的过程中，立方体底部与棋盘接触的那个面上的数字被加入总和 S。

LZYP 想要知道该怎样滚动这个正方体，才能使正方体从一个格子滚动到另一个格子得到 S 值最小。LZYP 想要知道这个最小值 S，当然他会告诉你起始格子和目标格子的坐标。

注意：立方体在起始格子和目标格子上的地面数字也要被计入总和，起始格子和目标格子是不同的。

为了刁难你，LZYP 决定问你 T个问题，当然每次你都需要正确告诉他答案是多少；否则他就会一直烦着你，那么你就无法安心刷水题了。

输入格式

输入数据第一行包含两个整数 N，T（分别用一个空格隔开），分别表示棋盘有 N 行N 列，共会有 T个问题；

第二行有6 个整数，表示立方体在开始格子上各个面上的 6 个数字，顺序是：前面、后面、上面、右面、下面、左面。这 6 个整数用空格隔开。

接下来 T行，每行四个整数 x1,y1,x2,y2，表示起始格子和目标格子的坐标（注意第一个是注意第一个是注意第一个是注意第一个是列号，第二个是行号）。输入数据保证会有一条路径从起始格子到达目标格子。

输出格式

输出数据总共 T行，每行一个整数 S，表示从起始格子到目标格子的最小和。

输入输出样例

5 1
0 8 1 2 1 1
5 2 5 3

5

2
5 1
1 1 1 1 1 1
1 2 2 3

3

样例解释

对于 Sample #1，一条可行的路径就是(5,2)(4,2)(4,1)(5,1)(5,2)(5,3)，底面的数字分别为 1,1,0,1,1,1。

对于 Sample #2，一条可行的路径就是(1,2) (2,2) (2,3)，底面的数字分别为 1,1,1。

数据规模

对于 20%的数据，N≤10，0≤W≤10；

对于 50%的数据，N≤50，0≤W≤100；

对于 100%的数据，N≤100，0≤W≤1000。

对于 100%的数据，T≤10.

提示

正方体的滚动是指，沿着底面与棋盘格子的一个公共边翻转。每个格子可以走多次，并且每走一次，需要累加相应的权值。