HaruCoder

※この問題の想定難易度はAtCoderの C問題上位～D問題、レーティング緑色レベルです。
ホーエン地方に存在するカナズミィ市とシダーケ町の間は山で隔てられています。
このままでは行き来がとても大変なので、両者の街をつなぐトンネルを掘る工事を行うことになりました。
ただし、街の住人たちはとてもせっかちなので、この工事はカナズミィ市側とシダーケ町側の両方からトンネルを掘り始めて工期を短くします。
また、街の住人たちはとても気分屋なのでトンネルを掘る速度が毎日変わります。
さらに、カナズミィ市とシダーケ町の間の山は地点によって幅が異なります。

この工事の責任者になったべーやん君の仕事はトンネル開通までの日数を計算することです。
山のいくつかの地点をトンネル開通候補地として、その工事にかかる日数を調べます。

• トンネル開通候補地の数$N$
• トンネル開通候補地$j$の山の横幅(必要なトンネルの長さ)$D_j$ m
• 工事を行う最大の期間 $M$ 日
• 工事を始めてから$i$日目にカナズミィ市側の人たちが掘る長さ$A_i$ m
• 工事を始めてから$i$日目にシダーケ街側の人たちが掘る長さ$B_i$ m

が与えられます。各候補地において、トンネルが開通するまでの日数を表示してください。
$M$日目まで工事を行ってもトンネルが開通しない場合は -1 を表示してください。

制約

• $1\le N\le {10}^5$
• $1\le D_j\le {10}^9$
• $1\le M\le {10}^5$
• $1\le A_i,B_i\le {10}^4$

入力

1行目にトンネル開通候補地の数$N$が与えられる。
2行目に候補地$j$の地点の山の横幅$D_j$が空白区切りで与えられる。
3行目に工事を行う最大の日数$M$が与えられる。
4行目にカナズミィ市側が$i$日目に掘る長さ$A_i$が空白区切りで与えられる。
5行目にシダーケ街側が$i$日目に掘る長さ$B_i$が空白区切りで与えられる。

トンネル開通候補地によらず、トンネルを掘る速度が変わらないことに注意してください。

出力

各トンネル開通候補地の工事にかかる日数を1行ずつ表示してください。

サンプル解説(入出力例1)

候補地が1つの場合、カナシダトンネル2 と同じ問題です。
毎日35mずつトンネルを掘るので、3日で地点1の山の横幅(100m)以上になります。

サンプル解説(入出力例2)

1日目はカナズミィ側で10m、シダーケ側で5m、合計15m掘られます。トンネルの長さは15mです。
2日目はカナズミィ側で15m、シダーケ側で10m、合計25m掘られます。トンネルの長さは40mです。
3日目はカナズミィ側で10m、シダーケ側で15m、合計25m掘られます。トンネルの長さは65mです。
4日目はカナズミィ側で15m、シダーケ側で20m、合計35m掘られます。トンネルの長さは100mです。
5日目はカナズミィ側で10m、シダーケ側で25m、合計35m掘られます。トンネルの長さは135mです。

地点1の横幅は70mであり、4日でトンネルが開通するので4を表示します。
地点2の横幅は120mであり、5日でトンネルが開通するので5を表示します。
地点3の横幅は10000mであり、5日間工事をしてもトンネルが開通しないので-1を表示します。