Sushi

回転寿司屋 JOI では寿司の乗った皿を環状のベルトコンベアで運んでいる．ベルトコンベアは反時計回 りに回っている．現在，店内には客 1 から客 N までの N 人の客がいて，客はベルトコンベアの周りに番 号順に反時計回りに並んでいる．客 N の隣には客 1 が座っている．

客は 1 人 1 枚ずつの皿を持っている．各皿には価格と呼ばれる値が定まっており，店を出る際に，客は， 自分の持っている皿の価格に等しい金額を支払う．

回転寿司屋 JOI では，一風変わったタイムセールを実施している．このタイムセールでは，Q 回に分け て，順番に板前から皿が提供される．i 回目 (1 ≦ i ≦ Q) の皿の提供の内容は 3 個の整数の組 (Si, Ti, Pi) で 表される． タイムセールのルールは次の通りである．タイムセールが始まる直前に，板前はベルトコンベア上の皿 を全て回収する．以下の 1～3 を i = 1, 2, . . . , Q まで繰り返す．

1. 板前がベルトコンベアの客 Si の前の位置に，価格 Pi の皿を置く．

2. 皿は客 Si の場所から客 Ti の場所までベルトコンベア上を移動する．それぞれの客は，自分の前の皿 に対し，次の行動を行う．

   • もし，その皿の価格が自分の持っている皿の価格より小さいならば，自分の皿とベルトコンベ ア上の皿を交換する．
   • もし，その皿の価格が自分の持っている皿の価格以上であれば，皿の交換は行わない．

3. 皿が客 Ti の前を通過した後，板前がその皿を回収する．

あなたは板前のもとで職人修業をしている弟子であり，店の皿洗いを任せられている．回転寿司屋 JOI の皿は価格によって洗い方が異なる．あなたは皿洗いの準備のために，タイムセールにおける Q 回の提供 において板前がどの価格の皿を回収するのかをあらかじめ知っておきたい．

Si = Ti のときは，客 Si のみが 2 つ目の行動を行う．

それぞれの客がタイムセールの直前に持っている皿の情報と，タイムセールにおける皿の提供の情報が 与えられたとき，それぞれの皿の提供で板前が回収する皿の価格を求めるプログラムを作成せよ．

標準入力から以下のデータを読み込め．

• 1 行目には，整数 N, Q が空白を区切りとして書かれている．これは，客の人数が N 人，タイムセー ルにおける皿の提供回数が Q 回であることを表す．
• 続く N 行のうちの i 行目 (1 ≦ i ≦ N) には，整数 Xi が書かれている．これは，客 i がタイムセールの 直前に価格 Xi の皿を持っていることを表す．
• 続く Q 行のうちの i 行目 (1 ≦ i ≦ Q) には，整数 Si, Ti, Pi が空白を区切りとして書かれている．これ は，i 回目の皿の提供が組 (Si, Ti, Pi) で表されることを表す．

出力は Q 行からなる．標準出力の i 行目 (1 ≦ i ≦ Q) には，i 回目の皿の提供で板前が回収する皿の価格 を表す整数を出力せよ．

• 1 ≦ N ≦ 400 000．
• 1 ≦ Q ≦ 25 000．
• 1 ≦ Xi ≦ 1 000 000 000 (1 ≦ i ≦ N)．
• 1 ≦ Si ≦ N (1 ≦ i ≦ Q)．
• 1 ≦ Ti ≦ N (1 ≦ i ≦ Q)．
• 1 ≦ Pi ≦ 1 000 000 000 (1 ≦ i ≦ Q)．