Description

有k头小肥猪，你每次要给他们一些饲料，重复n次。每次给的饲料用m个操作表示：

操作1：（1 x）给第x头猪一份饲料；

操作2：（2 x y）把第x头猪的饲料给第y头猪（第x头猪就没有饲料了）；

操作3：（3 x）把第x头猪的饲料加倍；

给你k、m、n和m个操作，回答操作过后每头猪有多少份饲料。

Input

第1行三个数：k、m、n；第2~m+1行每行一个操作。

1行m个数：操作后每头猪的饲料个数（模10000）。

3 4 3

1 3

1 2

2 3 1

3 2

3 14 0

HINT 【提示】

第一次操作后：1 2 0

第二次操作后：2 6 0

第三次操作后：3 14 0

【数据范围】

对于50%的数据：n≤10^4；

对于100%的数据：k≤10，m≤10，n≤10^10；