{"problem":{"name":"「蓬莱人形」","description":{"content":"为了证明人类的可能性，你需要解决一个问题。 给定序列 $a=[a_1,a_2,\\cdots,a_n]$。现在有 $q$ 次询问： - 每次给定二元组 $(x,y)$、模数 $m$，以及一个区间 $[l,r]$。求出有多少 $i\\in [l,r]$ 满足 $(a_i+x)\\bmod m<(a_i+y)\\bmod m$。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9212"},"statements":[{"statement_type":"Markdown","content":"为了证明人类的可能性，你需要解决一个问题。\n\n给定序列 $a=[a_1,a_2,\\cdots,a_n]$。现在有 $q$ 次询问：\n\n- 每次给定二元组 $(x,y)$、模数 $m$，以及一个区间 $[l,r]$。求出有多少 $i\\in [l,r]$ 满足 $(a_i+x)\\bmod m<(a_i+y)\\bmod m$。\n\n## Input\n\n第一行有两个正整数 $n, q$，表示序列长度及询问次数。\n\n第二行有 $n$ 个正整数 $a_1,a_2,\\cdots,a_n$，描述序列 $a$。\n\n接下来 $q$ 行，每行有五个整数 $l_i,r_i,x_i,y_i,m_i$，描述一组询问。\n\n## Output\n\n输出共 $q$ 行。第 $i$ 行输出第 $i$ 次询问的结果。\n\n[samples]\n\n## Background\n\n不老不死的妹红，还能称之为「人类」吗？\n\n超脱了生死的人类，本来就是不可思议的啊。\n\n## Note\n\n### 样例解释\n\n- 对于第一组询问，符合条件的元素的下标为 $1, 2, 7, 8$；\n- 对于第二组询问，没有符合条件的元素；\n- 对于第三组询问，符合条件的元素的下标为 $2, 3, 4, 5, 6, 7$；\n- 对于第四组询问，符合条件的元素的下标为 $5, 6, 9$；\n- 对于第五组询问，符合条件的元素的下标为 $1, 2$。\n\n### 数据范围及约定\n\n对于全部数据，$1\\le n\\le 10^5$，$1\\le q\\le 5\\times 10^5$，$1\\le a_i,x_i,y_i,m_i\\le 10^5$，$1\\le l_i\\le r_i\\le n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9212","tags":["O2优化","分块","根号分治","传智杯"],"sample_group":[["10 5\n4 3 2 5 8 5 3 3 1 2\n1 10 3 7 6\n4 10 5 5 4\n2 7 1 2 9\n5 9 3 4 7\n1 3 5 1 8","4\n0\n6\n3\n2\n"]],"created_at":"2026-03-03 11:09:25"}}