시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB35231058.824%

문제

$1$ 이상 $N$ 이하의 정수가 한 번씩 등장하는 길이 $N$의 수열 $A$가 주어진다.

수열 $A$에 대한 RMQ란 보통 Range Minimum Query 또는 Range Maximum Query를 뜻하는 말로, $1 \le l \le r \le N$인 $l$과 $r$이 주어졌을 때 $\min(A_l,\cdots\!,A_r)$ 또는 $\max(A_l,\cdots\!,A_r)$를 구하는 쿼리를 의미한다.

어느 쿼리도 포기하지 못했던 종영이는 새로운 RMQ를 만들기로 했다. 종영이가 새로 만든 RMQ(Range Mueonga Query)는 $RMQ(l,r)=\min(A_l,\cdots\!,A_r) \times \max(A_l,\cdots\!,A_r)$를 의미한다.

모든 쿼리 값들을 기억하기 위해, $N$행 $N$열의 2차원 배열 $B$에 대해 $i$행 $j$열의 위치에 해당하는 값 $B_{i,j}$에 $i \le j$라면 $RMQ(i,j)$를, $i>j$라면 $0$을 써 놓았다.

쿼리 중독증인 종영이는 이제 $B$에서 2차원 쿼리를 날리고 싶어졌다. 종영이를 위해 $1 \le l \le r \le N$이고 $1 \le s \le e \le N$인 네 정수 $l$, $r$, $s$, $e$가 주어질 때마다 $l \le i \le r$이고 $s \le j \le e$인 모든 $i$, $j$에 대해 $B_{i,j}$의 합을 구해주자.

입력

첫째 줄에 $N$과 $Q$가 공백으로 구분되어 주어진다. $(1 \le N \le 150\,000, 1 \le Q \le 150\,000)$

둘째 줄에 $A_1$, $\cdots$, $A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le N)$

셋째 줄부터 $Q$개의 줄에 걸쳐 쿼리들이 주어진다. 각 쿼리에서는 $l$, $r$, $s$, $e$가 공백으로 구분되어 주어진다. ($1 \le l \le r \le N$, $1 \le s \le e \le N$)

출력

각 줄에 쿼리의 답을 $10^9+7$로 나눈 나머지를 출력한다.

예제 입력 1

10 10
7 6 1 10 5 3 2 4 8 9
1 2 7 8
7 9 8 8
2 10 8 8
5 10 1 4
7 9 2 9
1 7 8 10
3 8 5 9
3 10 2 6
1 4 4 8
1 3 1 5

예제 출력 1

40
24
82
0
140
278
381
260
370
201
W3sicHJvYmxlbV9pZCI6IjIzMDUxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiUk1RIiwiZGVzY3JpcHRpb24iOiI8cD4kMSQgXHVjNzc0XHVjMGMxICROJCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1ZDU1YyBcdWJjODhcdWM1MjkgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YWUzOFx1Yzc3NCAkTiRcdWM3NTggXHVjMjE4XHVjNWY0ICRBJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzIxOFx1YzVmNCAkQSRcdWM1ZDAgXHViMzAwXHVkNTVjIFJNUVx1Yjc4MCBcdWJjZjRcdWQxYjUgUmFuZ2UgTWluaW11bSBRdWVyeSBcdWI2MTBcdWIyOTQgUmFuZ2UgTWF4aW11bSBRdWVyeVx1Yjk3YyBcdWI3M2JcdWQ1NThcdWIyOTQgXHViOWQwXHViODVjLCAkMSBcXGxlIGwgXFxsZSByIFxcbGUgTiRcdWM3NzggJGwkXHVhY2ZjICRyJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjICRcXG1pbihBX2wsXFxjZG90c1xcISxBX3IpJCBcdWI2MTBcdWIyOTQgJFxcbWF4KEFfbCxcXGNkb3RzXFwhLEFfcikkXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWNmZmNcdWI5YWNcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWIyOTAgXHVjZmZjXHViOWFjXHViM2M0IFx1ZDNlY1x1YWUzMFx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1ODhcdWIzNTggXHVjODg1XHVjNjAxXHVjNzc0XHViMjk0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBSTVFcdWI5N2MgXHViOWNjXHViNGU0XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHVjODg1XHVjNjAxXHVjNzc0XHVhYzAwIFx1YzBjOFx1Yjg1YyBcdWI5Y2NcdWI0ZTAgUk1RKFJhbmdlIE11ZW9uZ2EgUXVlcnkpXHViMjk0ICRSTVEobCxyKT1cXG1pbihBX2wsXFxjZG90c1xcISxBX3IpIFxcdGltZXMgXFxtYXgoQV9sLFxcY2RvdHNcXCEsQV9yKSRcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjZmZjXHViOWFjIFx1YWMxMlx1YjRlNFx1Yzc0NCBcdWFlMzBcdWM1YjVcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0LCAkTiRcdWQ1ODkgJE4kXHVjNWY0XHVjNzU4IDJcdWNjMjhcdWM2ZDAgXHViYzMwXHVjNWY0ICRCJFx1YzVkMCBcdWIzMDBcdWQ1NzQgJGkkXHVkNTg5ICRqJFx1YzVmNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YWMxMiAkQl97aSxqfSRcdWM1ZDAgJGkgXFxsZSBqJFx1Yjc3Y1x1YmE3NCAkUk1RKGksaikkXHViOTdjLCAkaSZndDtqJFx1Yjc3Y1x1YmE3NCAkMCRcdWM3NDQgXHVjMzY4IFx1YjE5M1x1YzU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZmZjXHViOWFjIFx1YzkxMVx1YjNjNVx1Yzk5ZFx1Yzc3OCBcdWM4ODVcdWM2MDFcdWM3NzRcdWIyOTQgXHVjNzc0XHVjODFjICRCJFx1YzVkMFx1YzExYyAyXHVjYzI4XHVjNmQwIFx1Y2ZmY1x1YjlhY1x1Yjk3YyBcdWIwYTBcdWI5YWNcdWFjZTAgXHVjMmY2XHVjNWI0XHVjODRjXHViMmU0LiBcdWM4ODVcdWM2MDFcdWM3NzRcdWI5N2MgXHVjNzA0XHVkNTc0ICQxIFxcbGUgbCBcXGxlIHIgXFxsZSBOJFx1Yzc3NFx1YWNlMCAkMSBcXGxlIHMgXFxsZSBlIFxcbGUgTiRcdWM3NzggXHViMTI0IFx1YzgxNVx1YzIxOCAkbCQsICRyJCwgJHMkLCAkZSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0Y1x1YjljOFx1YjJlNCAkbCBcXGxlIGkgXFxsZSByJFx1Yzc3NFx1YWNlMCAkcyBcXGxlIGogXFxsZSBlJFx1Yzc3OCBcdWJhYThcdWI0ZTAgJGkkLCAkaiRcdWM1ZDAgXHViMzAwXHVkNTc0ICRCX3tpLGp9JFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTc0XHVjOGZjXHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCAkTiRcdWFjZmMgJFEkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDEgXFxsZSBOIFxcbGUgMTUwXFwsMDAwLCAxIFxcbGUgUSBcXGxlIDE1MFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgJEFfMSQsICRcXGNkb3RzJCwgJEFfTiRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMSBcXGxlIEFfaSBcXGxlIE4pJDxcL3A+XHJcblxyXG48cD5cdWMxNGJcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwICRRJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1Y2ZmY1x1YjlhY1x1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWNmZmNcdWI5YWNcdWM1ZDBcdWMxMWNcdWIyOTQgJGwkLCAkciQsICRzJCwgJGUkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJDEgXFxsZSBsIFxcbGUgciBcXGxlIE4kLCAkMSBcXGxlIHMgXFxsZSBlIFxcbGUgTiQpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1YzkwNFx1YzVkMCBcdWNmZmNcdWI5YWNcdWM3NTggXHViMmY1XHVjNzQ0ICQxMF45KzckXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIzMDUxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiWWV0IEFub3RoZXIgUmFuZ2UgUXVlcnkgUHJvYmxlbSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiBhbiBhcnJheSAkQSQsIGNvbnNpc3Rpbmcgb2YgZGlzdGluY3QgaW50ZWdlcnMgaW4gdGhlIHJhbmdlJm5ic3A7JDEsMlxcZG90cyAsbiQuPFwvcD5cclxuXHJcbjxwPkxldCZuYnNwOyRCJCZuYnNwO2JlIGFuJm5ic3A7JG4gXFx0aW1lcyBuJCZuYnNwO21hdHJpeCwgd2hlcmUmbmJzcDskQl97aSwgan09XFxtaW4oQV9pLFxcZG90cyAsQV9qKSBcXHRpbWVzIFxcbWF4KEFfaSxcXGRvdHMgLEFfaikkJm5ic3A7aWYgJGkgXFxsZSBqJC4gT3RoZXJ3aXNlLCZuYnNwOyRCX3tpLGp9ID0gMCQuPFwvcD5cclxuXHJcbjxwPkdpdmVuJm5ic3A7JHEkJm5ic3A7cXVlcmllcyBvZiB0aGUgZm9ybSZuYnNwOyRsJCwgJHIkLCAkcyQsICRlJCwgcGxlYXNlIGNvbXB1dGUgdGhlIHZhbHVlJm5ic3A7JFxcc3VtX3t4PWx9XntyfVxcc3VtX3t5PXN9XmV7Ql97eCx5fX0kJm5ic3A7bW9kdWxvICQxMF45KzckLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzICRuJCZuYnNwO2FuZCAkcSQmbmJzcDsoJDEmbGU7biwgcSZsZTsxNTBcXCwwMDAkKS48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyZuYnNwOyRuJCZuYnNwO2Rpc3RpbmN0IGludGVnZXJzJm5ic3A7JEFfMSwgQV8yLCBcXGRvdHMgLCBBX24kJm5ic3A7KCQxJmxlO0FfaSZsZTtuJCkuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0ICRxJCZuYnNwO2xpbmVzIGVhY2ggY29udGFpbiBmb3VyIGludGVnZXJzJm5ic3A7JGwkLCAkciQsICRzJCwgJGUkLCB0aGUgJGkkLXRoIHN1Y2ggbGluZSBkZW5vdGluZyB0aGUgcGFyYW1ldGVycyBvZiB0aGUgJGkkLXRoIHF1ZXJ5LiAoJDEmbGU7bCZsZTtyJmxlO24kLCAkMSZsZTtzJmxlO2UmbGU7biQpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCAkcSQmbmJzcDtsaW5lcy4gT24gdGhlICRpJC10aCBsaW5lLCBvdXRwdXQgdGhlIGFuc3dlciBvZiB0aGUgJGkkLXRoIHF1ZXJ5LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=