题目描述

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的数字。丢失的数字用?来代替。

输出格式

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

样例

3
4??
?2
1

457
92
1

0002
002
02
2

4
???2
??2
?2
2

0002
002
02
2

提示

对于100%的数据，1≤n≤50。