题目描述

一天，小 Z 叫来他的 $n$ 个好朋友来玩一个游戏。小 Z 让他的 $n$ 个朋友从左往右坐成一排，他们面向右方，从左往右依次标号为 $1$ 到 $n$。每个人头顶上戴着一个黑帽子或一个白帽子， $i$ 号人可以看到 $i + 1$ 到 $n$ 号人的帽子的颜色。

每一轮开始时，小 Z 会告诉他的朋友们场上是否还有戴着黑帽子的人。每个人都十分聪明，如果他在该轮通过他已知的信息知道了自己帽子的颜色，那么他就会把自己的帽子放在自己的椅子上并起身离开。对于每个人，他能知道自己面前有哪几个人离开了，自己后面有多少个人离开了。

当所有人都离开时，游戏结束。

对于这个游戏，小 Z 有两种问题想考考你：

1. 如果给你这 $n$ 个人帽子颜色，求每个人的离开时间（离开时间指在第几轮离开）。
2. 如果给你这 $n$ 个人中一些人的离开时间，求每个人的帽子颜色。

输入格式

第一行两个正整数 $n,typ$。其中 $typ$ 表示询问类型。

若 $typ = 1$，接下来一行 $n$ 个非负整数，第 $i$ 个数 $c_i$ 表示 $i$ 号人的帽子颜色，$1$ 表示黑色，$0$ 表示白色；

若 $typ = 2$，接下来一行 $n$ 个非负整数，第 $i$ 个数 $t_i$ 表示 $i$ 号人的离开时间。如果 $t_i = 0$，表示 $i$ 号人的离开时间未知。

输出格式

输出一行 $n$ 个非负整数表示答案。

对于 $typ = 2$ 的情况，数据保证有解。如果有多解，输出任意一种即可。

样例1输入

5 1
0 0 1 0 0

样例1输出

4 4 3 4 4

样例2输入

5 2
0 0 1 1 0

样例2输出

0 0 0 0 0

样例3输入

5 2
0 0 2 2 0

样例3输出

1 0 0 0 0

样例4输入

5 2
0 0 0 0 0

样例4输出

0 0 0 0 0

样例5输入

4 2
0 9 0 4 

样例5输出

0 1 1 1 

样例6输入

10 2
15 16 0 0 12 0 0 8 0 0 

样例6输出

1 0 1 1 0 0 1 0 0 0 

为了选手更好的做题体验，我们提供了很多很多的样例。祝大家做题愉快。

数据范围

子任务编号	$n \leq$	$typ =$	特殊性质	子任务依赖	分值
1	$2000$	1			8
2	$2 \times 10^5$			1	12
3	$20$	2			10
4	$2000$			3	30
5	$2 \times 10^5$		保证 $t_i > 0$		10
6				4,5	30

对于所有的数据，满足 $ 1 \leq n \leq 2 \times 10^5 ,typ \in \{ 1,2 \} ,c_i \in \{ 0,1 \},0 \leq t_i \leq 10^{15} $。