Description

ACM比赛都有Ranklist(Standing),也就是排行榜。现在很多ACM的比赛会在最后一个小时封板。在此期间，版上只会显示每个队伍提交了哪些题和对应题的提交次数,但不会显示该队该题是否AC。 在ACMICPC比赛结束后，有些OJ会有刺激的刷版过程。刷版的过程是这样的：每次取有未判断题的队伍中排名最后的队伍，然后对他在封板后提交的题目取字典序最前的一题，给出AC与否，若AC，如排名可提前，则马上提前。再重复操作，到所有队都不再有未判断的题。 现在给你简约版的赛后未刷新的排行榜，排名榜只有队名和队伍题数，排名先按题数，题数相同则是队名字典序小的在前面。刷新操作每次判断一道题，告诉你操作的次数s，请你给出s次操作后的排行榜。

Input

多组数据,每组首先是队伍的个数n(0=0),再是该队还未判断的题数sumi，接下来一行是sum[i]个的数，代表该队每题真实的AC情况(已经按题号字典序排好)，1代表AC，0代表没AC。 最后是一个非负整数s(),代表刷版操作的次数.

Output

每组数据，输出s(小于500)次刷版操作后的排行榜，输出s行，每行先是队名，空一格后再是现在该队的题数。每组之间输出一个空行。

Sample

Input

5
longly 7 4
1 0 0 1
small 6 4
1 1 1 1
sqrt(3) 6 3
1 1 0
bag 5 1
0 
mountain 5 5
0 0 1 0 1
17

3
a 2 3
0 0 0
b 2 2
0 1
c 1 4
0 1 1 1
5

Output

small 10
longly 9
sqrt(3) 8
mountain 7
bag 5

b 3
c 3
a 2

Source: JQ