Description

题目背景

农夫琼斯庄园里的动物终于如愿赶走了琼斯，并把庄园改名为“动物农场”。作为一个民主政权，他们需要投票选出一个领导人。

题目描述

“动物农场”中共有n只动物，开始时每只动物投了一票，第i只投了xi，表示支持第xi只动物成为新的领导人。动物们一共进行了m次预选，第i次选取编号[li,ri]内的选民展开小规模预选，在该区间内获得超过区间大小一半的票的动物获胜，如果没有动物获胜，则由拿破仑钦定一位候选者si获得此次预选的胜利（获胜者可以不在该区间内），每次预选的结果需要公布出来，然后会有ki只动物决定将票改投向该次预选的获胜者。

Input Format

第一行两个整数，表示动物农场的动物数量n和预选次数m。 第二行n个整数，第i个数表示第i只动物投的票xi。 接下来m行，每行先有4个整数，分别表示li,ri,si,ki，si表示若此次预选没有动物获胜，视作编号为si的动物获得胜利，ki表示这次预选后改投的动物数，接下来ki个整数，分别表示决定改投的动物编号，可能重复，不保证有序。

Output Format

共m行，表示各次预选获胜的动物编号。

Sample

样例输入

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

样例输出

1
5
5
2

Hint

Hint