Minimum Road Count from the Capital

On a distant planet there are (n) countries numbered from 1 to (n) along with numerous bidirectional roads. However, the roads are too many to be listed individually. Instead, the roads are specified in the following format: a pair of intervals ((a,b),(c,d)) indicates that for any two countries (x) and (y) such that (a \le x \le b) and (c \le y \le d), there is a road connecting (x) and (y). The capital is located in country (P). Your task is to determine the minimum number of roads one must traverse to travel from country (P) to every other country. It is guaranteed that country (P) can reach every other country.

inputFormat

The first line contains three integers \(n\), \(m\), and \(P\) where \(n\) is the number of countries, \(m\) is the number of road descriptions, and \(P\) is the capital country.

Each of the following \(m\) lines contains four integers \(a\), \(b\), \(c\), and \(d\), representing a road description. This means that for any two countries \(x\) and \(y\), if \(a \le x \le b\) and \(c \le y \le d\), then there is a bidirectional road between \(x\) and \(y\).

outputFormat

Output a single line containing \(n\) integers. The \(i\)-th integer should be the minimum number of roads required to travel from country \(P\) to country \(i\) (with countries numbered from 1 to \(n\)).

sample

5 2 3
1 3 3 5
4 5 1 2

2 2 0 1 1