Маг Чариотис занимается выращиванием тыкв. Размер тыквы определяется целым числом (объёмом в кубических метрах).
У мага есть три заклинания: первое увеличивает размер любой тыквы *на* $p$, второе увеличивает размер любой тыквы *в* $k$ раз, а третье превращает тыкву размера ровно $m$ в карету (на тыквы других размеров оно не оказывает никакого влияния).
Изначально у мага есть $n$ тыкв и он планирует сделать как можно больше карет. Чтобы не колдовать попусту, ему хочется узнать, из каких тыкв возможно получить кареты, пользуясь только заклинаниями.
В первой строке записаны четыре целых числа: $n$, $p$, $k$, $m$ ($1 <= n <= 10^5$, $1 <= p <= 10^7$, $2 <= k <= 10^7$, $1 <= m <= 10^7$).
Во второй строке записаны $n$ целых чисел $a_i$ – начальные размеры тыкв, имеющихся у мага ($1 <= a_i <= 10^7$).
Выведите $n$ чисел, каждое из которых равно либо $0$, либо $1$. При этом, если из $i$-й тыквы можно получить карету, $i$-e число должно быть равно $1$, а если нельзя – то равняться $0$.
## Входные Данные
В первой строке записаны четыре целых числа: $n$, $p$, $k$, $m$ ($1 <= n <= 10^5$, $1 <= p <= 10^7$, $2 <= k <= 10^7$, $1 <= m <= 10^7$).Во второй строке записаны $n$ целых чисел $a_i$ – начальные размеры тыкв, имеющихся у мага ($1 <= a_i <= 10^7$).
## Выходные Данные
Выведите $n$ чисел, каждое из которых равно либо $0$, либо $1$. При этом, если из $i$-й тыквы можно получить карету, $i$-e число должно быть равно $1$, а если нельзя – то равняться $0$.
## Примеры
Входные данные1 3 2 7
2
Выходные данные1 Входные данные9 2 4 8
1 2 3 4 5 6 7 8 9
Выходные данные1 1 0 1 0 1 0 1 0
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the required total duration of the song.
Let $ A \in \mathbb{Z} $ be the duration of the chorus.
Let $ B \in \mathbb{Z} $ be the duration of each verse.
Let $ N \in \mathbb{Z}_{\geq 0} $ be the number of interludes.
Let $ S = (s_1, s_2, \dots, s_N) $ be the sequence of interlude durations, where $ s_i \in \mathbb{Z} $ and $ 1 \leq s_i \leq 500 $.
Let $ x \in \mathbb{Z}_{\geq 0} $ be the number of verses to be composed.
Let $ y \in \mathbb{Z}_{\geq 0} $ be the number of times the chorus is repeated.
Let $ z \subseteq \{1, 2, \dots, N\} $ be a subset of interludes used (possibly empty).
**Constraints**
1. $ 1 \leq T \leq 10^{18} $
2. $ 1 \leq A, B \leq 500 $
3. $ 0 \leq N \leq 500 $
4. $ 1 \leq s_i \leq 500 $ for all $ i \in \{1, \dots, N\} $
5. The song structure must alternate between chorus and verse, starting and ending with chorus:
$$
\text{Structure: } \underbrace{A,\, \text{interlude?},\, B,\, \text{interlude?},\, A,\, \dots,\, A}_{\text{starts and ends with } A}
$$
Hence, if there are $ x $ verses, there must be exactly $ x + 1 $ choruses.
6. The total duration is:
$$
T = (x + 1) \cdot A + x \cdot B + \sum_{i \in z} s_i
$$
7. The subset $ z $ of interludes used must satisfy $ |z| \leq N $, and each $ s_i $ may be used at most once.
**Objective**
Find the minimum $ x \in \mathbb{Z}_{\geq 0} $ such that there exists a subset $ z \subseteq \{1, \dots, N\} $ with:
$$
(x + 1) \cdot A + x \cdot B + \sum_{i \in z} s_i = T
$$
If no such $ x $ exists, output $ -1 $.