题目描述

有一片长度为 $n$ 的雷区，编号为 $1 \sim n$。扫雷小队会用一种探测器扫描每个区域，获取每块区域的危险程度 $a_i$。如果某块区域的危险程度不低于 $x$，就说明这块区域下面很有可能埋藏着地雷，此时需要向这块区域上喷洒一种腐蚀剂，降低危险程度。

在第 $i$ 块区域喷洒腐蚀剂会产生以下影响：

• 使这块区域的危险程度降低至原来的四分之一（向下取整）；
• 使第 $i-1$ 和第 $i+1$ 块区域的危险程度降低至原来的三分之一（向下取整）；
• 使第 $i-2$ 和第 $i+2$ 块区域的危险程度降低至原来的一半（向下取整）。

每块区域至多被探测一次。

现在你是扫雷小队的一名成员，按照编号顺序对每个区域进行扫雷工作，求扫雷完成后每块区域的危险程度。

输入格式

第一行：输入一个整数 $n(1≤n≤1000)$，表示区域的个数。

第二行：$n$ 个整数 $a_1,a_2...a_n(0≤a_i≤100)$，表示每个区域的危险程度。

第三行：一个整数 $x(1≤x≤100)$，表示危险程度阈值。

输出格式

在一行中输出 $n$ 个整数，分别表示扫雷完成后每块区域的危险程度。

样例

5
0 0 20 99 98
20

0 0 1 8 16