题目描述

FJ 农场里每一只奶牛的脖子上挂着一个胸牌，胸牌上面印着一个倒三角数字塔，例如奶牛 Bessie 脖子上的胸牌印着：

74932
1325
457
92
1

你发现什么规律了吗？除了第一行的数字外，其他行的数字都等于其正上方的数字 + 其右上方数字的和，再除以 10 之后的余数。看不懂？除了第一行之外，我们用 a[i][j] 表示第i行第j列的数字，那么 a[i][j] = (a[i-1][j]+a[i-1][j+1])%10 。我们规定 i 从上到下是递增的，j 从左往右是递增的。

所有奶牛的胸牌都符合这个规律！！除了第一行之外，a[i][j] = (a[i-1][j]+a[i-1][j+1])%10。
奶牛 John 是个粗心的家伙，它在玩耍的过程中，胸牌上面的数字大部分都弄丢了，John 胸牌的每一行都只剩下一个数字！其他数字都丢失了。假如我们用 ‘?’ 来表示一个丢失的数字，那么 John 的胸牌可能变成这样了：

4??
?2
1

农夫知道后非常生气，打算不给 John 发圣诞礼物，除非 John 可以还原胸牌。John 希望你能帮助它还原胸牌，你能做到呢？

输入格式

第一行，一个整数 $n$ ，表示数字塔共有 $n$ 行:

第 1 行有 $n$ 个数字

第 2 行有 $n-1$ 个数字

第 3 行有 $n-2$ 个数字,

......

第 i 行有 $n-i+1$ 个数字

最后一行只有一个数字。这些数字都是 0 至 9 的数字。丢失的数字用 ? 来代替。

数据范围

对于 100 %的数据， $1 \le n \le 50$。

输出格式

输出 John 的胸牌，也就是你要输出一个倒三角数字塔。请放心，答案肯定唯一。

样例

3
4??
?2
1

457
92
1

4
???2
??2
?2
2

0002
002
02
2