题目描述

小 E 有 $n$ 种颜色的球，其中第 $i$ 种有 $a_i$ 个。

有两类工具：

• 第一类：可以把一个指定颜色的球变成一个任意颜色的球
• 第二类：可以把一个指定颜色的球变成两个这种颜色的球

一个变化之后的球也可以通过工具产生新的变化。

关于第 $i$ 种颜色的第一类工具有 $b_i$ 个，第二类工具有 $c_i$ 个。

如果每一个工具最多只能使用一次，那么：

1. 对于每种颜色 $i$，第 $i$ 种颜色的球最后最多能有多少个
2. 小 E 最后最多能有多少个球

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个整数，其中第 $i$ 个表示 $a_i$。

第三行 $n$ 个整数，其中第 $i$ 个表示 $b_i$。

第四行 $n$ 个整数，其中第 $i$ 个表示 $c_i$。

输出格式

第一行 $n$ 个整数，其中第 $i$ 个表示第 $i$ 种颜色的球最后最多有多少个。

第二行一个整数，表示小 E 最后最多能有多少个球。

样例

输入：

2
1 2
1 2
1 0

输出：

4 3
4

数据范围

• $1 \le n \le 351493$
• $0 \le a_i, b_i, c_i \le 10^9$