Time-Traveling Flight Schedule

Bessie is on vacation and is taking advantage of technologically advanced, time‐traveling flights! There are \(N\) airports numbered \(1,2,\ldots,N\) and \(M\) flights. Flight \(j\) departs from airport \(c_j\) at time \(r_j\) and arrives at airport \(d_j\) at time \(s_j\) (where \(0 \le r_j, s_j \le 10^9\); note that \(s_j < r_j\) is allowed).

Each airport \(i\) requires a layover of \(a_i\) time units (\(1 \le a_i \le 10^9\)). That is, if Bessie arrives at airport \(i\) at time \(s\), she can only catch a flight departing at time \(r\) if \(r \ge s + a_i\). Bessie starts at airport 1 at time 0.

Your task is to determine the earliest time Bessie can arrive at each airport from 1 to \(N\). If an airport is unreachable, output \(-1\) for that airport.

Note: The time limit for this problem is 4 seconds, twice the default.

inputFormat

The first line contains two integers \(N\) and \(M\) representing the number of airports and flights.

The second line contains \(N\) integers \(a_1, a_2, \ldots, a_N\), where \(a_i\) is the layover time required at airport \(i\).

Each of the next \(M\) lines contains four integers \(c_j, r_j, d_j, s_j\), where flight \(j\) departs from airport \(c_j\) at time \(r_j\) and arrives at airport \(d_j\) at time \(s_j\).

outputFormat

Output \(N\) space-separated integers. The \(i\)-th integer is the earliest time Bessie can arrive at airport \(i\); if an airport is unreachable, output \(-1\) for that airport.

sample

1 0
5

0