{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"风非常喜欢漂亮的狗,她养了n只宠物狗。所以嘉嘉每天都要替风喂狗。嘉嘉爱风,但不爱狗,所以嘉嘉用特殊的方式喂狗。在午餐时间,狗们会站成一排,从1到n编号,最左边的是1,第二只是2,依此类推。在每次喂食时,嘉嘉会选择一个区间[i,j],然后选择第k只漂亮的狗来喂食。当然,嘉嘉有自己的方式来决定每只狗的漂亮值。需要注意的是,嘉嘉不想喂食同一个位置太多次,因为这可能会导致一些狗的死亡。如果这样的话,风会生气,后果会很严重。因此,任何喂食区间都不会完全包含另一个,尽管这些区间可能会相互交叉。\r\u003cbr\u003e\r\u003cbr\u003e你的任务是帮助嘉嘉计算每次喂食后哪只狗吃了食物。"}},{"title":"输入","value":{"format":"HTML","content":"第一行包含n和m,表示狗的数量和喂食次数。\r\u003cbr\u003e\r\u003cbr\u003e第二行包含n个整数,描述每只狗的漂亮值,从左到右。你应该注意,漂亮值较低的狗更漂亮。\r\u003cbr\u003e\r\u003cbr\u003e接下来的m行每行包含三个整数i,j,k,表示嘉嘉在这次喂食中喂了第k只漂亮的狗。\r\u003cbr\u003e\r\u003cbr\u003e你可以假设n\u0026lt;100001且m\u0026lt;50001。"}},{"title":"输出","value":{"format":"HTML","content":"输出文件有m行。第i行应包含第i次喂食后得到食物的狗的漂亮值。"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7 2\r\n1 5 2 6 3 7 4\r\n1 5 3\r\n2 7 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}