题目描述

噜噜 想要变得强壮！在经过一番深思熟虑之后，他决定——不停的吃，先把营养给补充上来。

在接下来的 $n$ 天里噜噜每天都会吃掉营养价值为$a_i$的食物，可惜的是噜噜一天当中所能吸收的营养是有限的：

• 如果噜噜某天吃掉的食物营养价值不超过$10^4$，他能获得这些食物当中全部的营养。

• 如果噜噜某天吃掉的食物营养价值超过$10^4$但不超过$5 * 10^4$，他只能获得这些食物当中$70\%$的营养（向下取整）。

• 如果噜噜某天吃掉的食物营养价值超过$5 * 10^4$，他只能获得这些食物当中$50\%$的营养（向下取整）。

输入格式

第一行一个整数$n$，表示噜噜计划补充营养的$n$天。

接下来一行$n$个整数，表示噜噜当天吃掉的食物营养价值。

输出格式

输出$n$行，每行一个整数，表示噜噜每天能够吸收的食物营养价值。

样例 #1

样例输入 #1

5
1 100 1001 50001 1000000009

样例输出 #1

1
100
1001
25000
500000004

提示

【数据范围】

本题中，double类型不会有精度问题。

对于所有数据：$1 \leq n \leq 10^5$