日本が冬であるこの時期，南半球にあるオーストラリアでは暑い日が続いている．オーストラリアに住む IOI 君は，ある D 日間の天気予報をもとに，着る服の計画を立てることにした．i 日目 (1 ≦ i ≦ D) の最高気温は T_i 度であると予報されている．

IOI 君は N 種類の服を持っており，それらには 1 から N までの番号がついている．服 j (1 ≦ j ≦ N) は最高気温が A_j 度以上 B_j 度以下の日に着るのに適している．また，それぞれの服には「派手さ」とよばれる整数が定まっており，服 j の派手さは C_j である．

D 日間のそれぞれに対し，IOI 君は，最高気温が天気予報に従ったときに着るのに適した服のうち 1 つを着る服として選ぶ．同じ服を何度選んでもよいし，D 日間で一度も選ばれない服があってもよい．

더운 날들 (Hot days) timer 1s memory 64MB

더운 날들 (Hot days) 1s 64MB