Sóc nâu

Một ngày nọ, Sóc Nâu tỉnh dậy giữa một dãy núi dài với \(N\) đỉnh núi, được đánh số từ \(1\) đến \(N\). Mỗi đỉnh núi có độ cao là \(a_i\), với \(1 \le i \le N\). Sóc Nâu hiện đang đứng tại đỉnh núi số \(S\).

Vốn là một vận động viên leo núi dày dạn, Sóc Nâu có thể nhảy sang đỉnh bên trái hoặc bên phải, miễn là độ chênh lệch độ cao giữa hai đỉnh không quá mức cho phép. Cụ thể, từ đỉnh \(i\), Sóc Nâu có thể nhảy sang đỉnh \(j\) nếu \(|a_i - a_j| \le K\).

Bạn hãy giúp Sóc Nâu xác định những đỉnh núi nào mà chú có thể đến được, bắt đầu từ đỉnh \(S\).

Input

• Dòng đầu tiên chứa ba số nguyên dương \(N\), \(K\), \(S\) \((1 \leq N \leq 10^5,\ 1 \leq K \leq 10^9,\ 1 \leq S \leq N)\) --- số lượng đỉnh núi, độ chênh lệch tối đa cho phép, và vị trí ban đầu của Sóc Nâu.
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) \((1 \leq a_i \leq 10^9)\) --- độ cao của các đỉnh núi.

Output

In ra một dòng gồm \(N\) số, mỗi số là \(0\) hoặc \(1\). Số thứ \(i\) là \(1\) nếu Sóc Nâu có thể đến được đỉnh \(i\), ngược lại là \(0\).

Example

5 1 2
3 2 3 5 2

1 1 1 0 1 

Scoring

• Subtask 2 (30 điểm): \(N \leq 1000\).
• Subtask 3 (70 điểm): Không có ràng buộc bổ sung.