题目描述

薯条哥商店里只卖两种商品，“可乐“和“薯条”。

现在有$n$个人来到商店购物，第$i$个人有一个喜好区间$[l_i,r_i]$和购买目标商品，他只看货架上位于区间里的商品，并从中挑选$k_i$个保质期最长的可乐或者薯条买走(如果有多个商品保质期相同，他会拿走区间中靠前的那个)。你能告诉薯条哥每个人买走的商品编号吗。

输入描述

第一行输入两个整数$n$和$m(1≤n,m≤10^5)$代表来薯条哥商店购物的人数和商品数量。

第二行输入$m$个整数$a_1, a_2,...,a_m(1≤a_i≤10^9)$代表商品的保质期。

第三行输入$m$个整数$b_1,b_2,...,b_m(0≤b_i≤1)$代表商品的种类，其中，$b_i=0$代表"可乐"、$b_i=1$代表"薯条''。

此后$n$行，第$i$行输入四个整数$l_i,r_i,t_i,k(1\le l_i\le r_i\le m;0\le t_i\le 1;1\le k_i\le m)$代表第$i$个人的喜好区间、购买商品和购买件数。

其中，$t_i$=0代表他想要购买“可乐”、$t_i=1$代表他想要购买“薯条”。

输出描述

输出$n$行，第$i$行包含至多$k_i$个整数，代表第$i$个人购买的商品编号(如果有多个商品保质期相同，输出编号较小的那个)，你需要按照从小到大的顺序依次输出;如果没有买到足够的商品，使用一个$-1$替代。

样例

输入

5 5
2 3 4 5 6
1 1 0 1 1
1 3 1 2
1 3 1 2
1 3 0 5
1 5 1 1
1 5 0 1

输出

2 1
-1
3 -1
5
-1

样例解释

第一次询问，货架上的情况为$[2,3,*,5,6]$ (*代表非目标商品，下划线代表喜好区间)，先买第二件，再买第一件;

第二次询问，货架上的情况为$[x,x,*,5,6]$($x$代表已售罄商品)，此时无法购买，直接输出$-1$;

第三次询问，货架上的情况为$[*,*,4,5,6]$由于只剩一件商品，故先购买第三件，后输出$-1$代表没有买到足够数量的商品。