在餐厅度过了一个美好的夜晚后,是时候回家了。莱哈作为一位真正的绅士建议努拉载她一程。当然,女孩很高兴地同意了。突然出现了一个问题:Leha 在餐厅附近的一个巨大停车场找不到他的车。于是他决定向看守人寻求帮助。
停车可以正式表示为 109 × 109 的矩阵。矩阵的每个单元格中恰好有一辆车。所有汽车都有自己的机器编号,以正整数表示。让我们从左到右用 1 到 109 的整数对矩阵的列进行索引,从上到下用 1 到 109 的整数对矩阵的行进行索引。巧合的是,对于每个单元格 (x, y),该单元格中的汽车数量等于最小正整数,而该最小正整数在单元格 (i, y) 和 (x, j) 中找不到,1 ≤ i < x,1 ≤ j < y。
停车场左上片段5×5
Leha想要向看守人询问q请求,这可以帮助他找到他的车。每个请求都表示为五个整数 x1、y1、x2、y2、k。看守人必须考虑矩阵的所有单元格 (x, y),使得 x1 ≤ x ≤ x2 且 y1 ≤ y ≤ y2,并且如果单元格 (x, y) 中的汽车数量不超过 k,则将请求的答案增加单元格 (x, y) 中的汽车数量。对于每个请求,Leha 都会要求看守人告诉他最终的金额。由于总和可能非常大,黑客要求以 109 + 7 为模进行计算。
然而,这些请求对于看守人来说似乎不切实际。帮助看守人回答莱哈的所有请求。
输入
第一行包含一个整数 q (1 ≤ q ≤ 104) — Leha 的请求数。
接下来的 q 行包含五个整数 x1, y1, x2, y2, k (1 ≤ x1 ≤ x2 ≤ 109, 1 ≤ y1 ≤ y2 ≤ 109, 1 ≤ k ≤ 2·109) - Leha 请求的参数。
输出
精确打印 q 行 — 在第一行中打印第一个请求的答案,在第二行中打印第二个请求的答案,依此类推。
示例
输入 #1
4 1 1 1 1 1 3 2 5 4 5 1 1 5 5 10000 1 4 2 5 2
输出 #1
1 13 93 0
注意
让我们分析一下所有的请求。在每种情况下,请求的子矩阵都以蓝色突出显示。
在第一个请求 (k = 1) 中,Leha 仅询问左上角的停车位。在这个单元格中,汽车的编号是 1。因此答案是 1。
在第二个请求 (k = 5) 中,合适的数字是 4, 1, 2, 3, 2, 1。因此答案是 4 + 1 + 2 + 3 + 2 + 1 = 13。
在第三个请求 (k = 10000) 中,Leha 询问停车的左上角框架 5 × 5。由于 k 足够大,所以答案等于 93。
在最后一个请求(k = 2)中,cur 的数字都不合适,因此答案为 0。