There are $ n $ towns in Byteotia, numbered 1 through $ n $. Highways are built in the country not too often; if they are built, however, they are built in bigger batches. Thus $ m $ batches have been built, the $ i $-th batch consists of all highways connecting towns with numbers in $[ a_{i}, b_{i} ]$ with towns with numbers in $[ c_{i}, d_{i} ]$. The highways cross only at the towns, but they may lead through tunnels or flyovers. Using the highway network one can travel between any pair of towns in Byteotia. Riding a single highway costs exactly 1 bytean dollar.

Byteasar spent the last several years abroad. This year he has decided to return to his home country and buy a house in the capital of the country, Bitcity. He is planning to visit all his old acquaintances that now live in many different towns of Byteotia. He would like to know what is the cheapest route from Bitcity to any other town in Byteotia (using only the highway network). Help him find that out.

Input Format

The first line of the standard input contains three integers $ n $, $ m $ and $ p $ ($2 \le n \le 500\,000$, $1 \le m \le 100\,000$, $1 \le p \le n $) that represent the number of towns in Byteotia, the number of batches of highways that have been built and the number of the town where Byteasar lives (that is, Bitcity). The following $ m $ lines contain a description of the batches, one per line. Each such description consists of four integers $ a_{i} $, $ b_{i} $, $ c_{i} $, $ d_{i} $ ($1 \le a_{i} \le b_{i} \le n $, $1 \le c_{i} \le d_{i} \le n $, $[ a_{i}, b_{i}] \cap [ c_{i}, d_{i} ] = \varnothing$). It means that from each of the towns $ a_{i}, \ldots, b_{i} $ leads a bidirectional highway to each of the towns $ c_{i}, \ldots, d_{i} $. Each highway appears in at most one batch.

Output Format

Your program should write $ n $ lines to the standard output. The $ i $-th line should contain the minimal cost, in bytean dollars, of travelling from Bitcity to the $ i $-th town of Byteotia. The $ p $-th of these lines should contain the number 0.

Example

Input

5 3 4
1 2 4 5
5 5 4 4
1 1 3 3

Output

1
1
2
0
1