등불

농부 존은 소 떼를 데리고 알프스로 하이킹을 떠났습니다. 밤이 되어 하이킹은 끝났습니다. 하지만 소 몇 마리가 산맥 곳곳에 갇혀 있어서, 존이 그 소들을 모두 구해야 합니다.

산맥은 수직 2차원 평면 위의 $n$개 점으로 나타냅니다. 이 점들을 봉우리라고 부릅니다. 봉우리는 $1$번부터 $n$번까지 순서대로 번호가 매겨져 있습니다. 봉우리 $i$의 좌표는 $(i, h_i)$이고, $h_i$는 봉우리 $i$의 고도입니다. $h_1, h_2, \dots, h_n$은 $1$부터 $n$까지의 순열입니다. 즉 각 $j = 1, \dots, n$에 대해 $h_i = j$를 만족하는 $i \in \{1, \dots, n\}$이 정확히 하나 있습니다.

$1 \le i < n$인 각 $i$에 대해, 봉우리 $i$와 $i+1$은 직선 선분으로 이어져 있습니다.

밤이라서 존은 작동하는 등불을 적어도 하나 가지고 있어야만 걸을 수 있습니다. 판매 중인 등불은 $k$개입니다. 등불 $j$는 봉우리 $p_j$에서 $c_j$프랑에 살 수 있습니다. 이 등불은 존의 고도가 $[a_j, b_j]$ 범위 안에 있을 때만 작동합니다. 고도가 $a_j$보다 작거나 $b_j$보다 크면 등불 $j$는 꺼집니다. 등불은 범위를 벗어난다고 고장 나지 않습니다. 존이 범위 안의 고도로 돌아오면 다시 켜집니다.

존이 봉우리 $p$에 있을 때 할 수 있는 행동은 다음 세 가지 중 하나입니다.

• 봉우리 $p$에서 살 수 있는 등불 중 하나를 구매합니다. 한 번 산 등불은 계속 쓸 수 있습니다.
• $p > 1$이면 봉우리 $p-1$로 걸어갑니다.
• $p < n$이면 봉우리 $p+1$로 걸어갑니다.

존은 작동하는 등불 없이 움직여서는 안 됩니다. 인접한 두 봉우리 사이는 걷는 모든 순간에 이미 가진 등불 중 하나 이상이 작동할 때만 걸을 수 있습니다. 걷는 내내 같은 등불일 필요는 없습니다.

예를 들어 존이 고도 $4$인 봉우리에 있고, 고도 $1$인 인접 봉우리로 가려고 합니다. 존이 $[1, 3]$과 $[3, 4]$ 구간에서 작동하는 등불을 가지고 있다면 걸을 수 있습니다. 하지만 $[1, 1]$과 $[2, 5]$ 구간에서만 작동하는 등불을 가지고 있다면, 고도 $1.47$에서 작동하는 등불이 없으므로 걸을 수 없습니다.

각 $j$에 대해 $a_j \le h_{p_j} \le b_j$이면, 존이 봉우리 $p_j$에서 등불 $j$를 먼저 사고 탐색을 시작한다고 합시다. 그다음 위의 세 행동만으로 $n$개 봉우리를 모두 최소 한 번씩 방문해야 합니다. 이런 각 $j$에 대해, 산맥 전체를 탐색하기 위해 존이 써야 하는 최소 금액을 구하십시오. 비용에는 등불 $j$의 구매 금액이 포함됩니다.

첫째 줄에 $n$과 $k$가 주어집니다($1 \le n \le 2000$, $1 \le k \le 2000$). 둘째 줄에는 $h_1, h_2, \dots, h_n$이 주어집니다($1 \le h_i \le n$). 이 값들은 $1$부터 $n$까지의 순열입니다.

다음 $k$개 줄 중 $j$번째 줄에는 네 정수 $p_j$, $c_j$, $a_j$, $b_j$가 주어집니다($1 \le p_j \le n$, $1 \le c_j \le 10^6$, $1 \le a_j \le b_j \le n$). 각각 등불 $j$를 살 수 있는 봉우리, 가격, 작동 고도 범위입니다.

각 $j$에 대해 한 줄을 출력합니다.

• $h_{p_j}$가 $[a_j, b_j]$ 범위 밖이면 $-1$을 출력합니다.
• 그렇지 않은데 등불 $j$를 먼저 산 뒤 산맥 전체를 탐색할 수 없으면 $-1$을 출력합니다.
• 그 밖의 경우에는 존이 등불 $j$를 먼저 사고 산맥 전체를 탐색하는 데 드는 최소 금액을 출력합니다.

존이 봉우리 $3$에서 등불 $1$을 먼저 사면, 다음과 같이 움직일 수 있습니다.

• 왼쪽으로 두 번 걸어 봉우리 $1$로 갑니다.
• 등불 $2$를 삽니다.
• 오른쪽으로 걸어 봉우리 $4$로 갑니다.
• 등불 $3$을 삽니다.
• 오른쪽으로 걸어 봉우리 $7$로 갑니다.

이 시점에 존은 모든 봉우리를 적어도 한 번 방문했고, 총 $1 + 2 + 4 = 7$프랑을 썼습니다.

등불 $2$, $6$, $7$은 판매 봉우리의 고도에서 작동하지 않으므로 처음 살 수 없습니다. 이 등불들의 답은 모두 $-1$입니다.

등불 $3$이나 $4$로 시작하면 다른 등불을 더 사지 않고도 모든 봉우리를 방문할 수 있습니다.

등불 $5$로 시작하면 나중에 등불 $4$도 사야 합니다.

등불 $8$로 시작하면 봉우리 $7$에서 막힙니다. 등불 $7$도 추가로 사더라도, 봉우리 $7$에서 봉우리 $6$으로는 걸어갈 수 없습니다.