On the occasion of the 50th anniversary of the liberation of the South and the reunification of the country, Bi had the opportunity to travel to Ho Chi Minh City with his parents to watch the military parade and drone show. Bi's family rented a private car to make traveling through all n districts of the city more convenient. It is known that the hotel where Bi is staying is located in district s, and this is also where the family begins their journey. Since traveling between districts via one-way roads requires tickets, Bi wants to help his parents choose the most efficient route to save costs. At the start, the family has not yet purchased any tickets for traveling through the one-way roads. It is known that there are q tickets, belonging to one of the following three types:
- Type 1: Purchase a one-way ticket to travel from district u to district v.
- Type 2: Purchase a one-way ticket to travel from district u to any district in the range from l to r.
- Type 3: Purchase a one-way ticket to travel from any district in the range from l to r to district u.
As Bi wants to visit all the districts, he wants to calculate, for each district, the minimum cost to reach that district when starting from the hotel. (Each district visit is considered independent and if there are no ways to purchase tickets to arrive to the district then output −1.)
### Input
- The first line consists of three positive integers n,q và s.
- The next q lines each contain a positive integer t which is 1, 2, or 3, describing the type of ticket. After that comes the positive integer u (along with v, l, or r depending on the ticket type), and finally w, indicating the ticket price.
### Output
- Print n numbers, each separated by a space, where the i-th number represents the minimum cost to travel from the hotel to district i.
### Constraints
- 1≤n,q≤105,1≤s≤n.
- 1≤u,v≤n,1≤w≤109.
- 1≤l≤r≤n.
### Example
Input:
35123236923226822233333115513369
Output:
012355
