题目描述

在某平行空间内，你是一个互联网公司的老板。又到了10月24日程序员节（1024=2¹⁰），给你的n个员工普遍增加工资的日子。这次的规则如下：

名单前面三分之一（人数截尾取整数）的员工增加工资1024元；

名单中间三分之一（人数截尾取整数）的员工增加工资10.24%（如果是小数就截尾取整数）；

剩余的员工工资增加为原来的两倍。

打印现在每个员工的工资。

输入格式

输入有两行。

第一行，一个整数n，表示员工的人数，10≤n≤10000。


第二行，n个整数，表示原来每个员工的工资。每两个数之间用空格隔开。

输出格式

输出一行，n个整数，表示现在每个员工的工资。

每两个整数之间用一个空格隔开。


每行前后没有多余的空格。


最后有一个换行。

样例

input

10
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

output

2024 3024 4024 4409 5512 6614 14000 16000 18000 20000

提示

熟练应用循环的初值和终值来控制下标的变化。