{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eNancy used to be known for its Art Nouveau quarter, the rum baba and good King Stanislas Leszczynski, the deposed Polish king who gave the city its gorgeously frilly architectural centrepiece in the 18th century.\u003c/p\u003e\u003cp\u003eBut in 2013, Nancy rediscovered its Renaissance past, with events and exhibitions all around town this summer, from the fine art museum to the thermal establishment and the botanical gardens. Now it is time for me to discover the old town\u0027s Renaissance relics and the Utopian town-planning schemes of Duke Charles III, from the days when Nancy was capital of a powerful independent duchy at the crossroads between northern and southern Europe.\u003c/p\u003e\u003cp\u003eThe old and new towns are seamlessly connected today. The new city or Ville Neuve laid out in 1588 is still the commercial heart of the city with its shops and banks, and covered by food markets in the street near the square originally planned for the cathedral.\u003c/p\u003e\u003cp\u003eIn this autumn, I have the privilege of spending a several-months-long holiday in Ville Neuve. Daily contemplations always follow the breakfasts together with baguettes\u0027 sweet and smooth. What makes a baguette better is not La vache qui rit cheese, but where I get it. But why should people who program computers be so concerned about the number of food markets in a street? I do label those food markets which supply baguettes in the street from $$$1$$$ to $$$n$$$.\u003c/p\u003e\u003cp\u003eAt each glimmering daybreak came, I carry several one-euro coins and make a plan to visit several consecutive food markets. Regardless of winds and rains, a food market always offers a fixed number of baguettes at a fixed price. Two different food markets may be different: The numbers of their daily baguettes offered and the prices differ.\u003c/p\u003e\u003cp\u003eThe early bird catches the worm. Since there is no need to worry about other customers, enough money makes me free to buy all the baguettes in a food market or be blind and go to the next market.\u003c/p\u003e\u003cp\u003eBut why should people just like you be so concerned about the number of different ways that I have to purchase baguettes? They even double-check with me that I may cost nothing and starve, or spend any amount of money that I have. As what theorists always say in a knapsack-like problem, two ways to purchase baguettes are different if, at some markets, the numbers of baguettes purchased vary.\u003c/p\u003e\u003cp\u003eA man who pursuits high efficiency like you tries to tell me the number of ways I have once he confirmed the amount of money I carry and my visit plan day after day. An undisciplined man like me, though I have made a long list of plans for all days, decides to make a new plan for the next day once I received your reply about one day. I use $$$lastans$$$ to denote the number in your reply and set it to zero before my first day in Ville Neuve.\u003c/p\u003e\u003cp\u003eOn a day, I check what I made in the original plan, say $$$l\u0027$$$ and $$$r\u0027$$$ the index of the first food market I decided to visit, and of the last one, and say $$$c$$$ the number of one-euro coins I decided to carry. A transformation like an encryption\u003c/p\u003e\u003cp\u003e$$$$$$l \u003d \\min\\{((l\u0027 + lastans) \\bmod n) + 1, ((r\u0027 + lastans) \\bmod n) + 1\\}$$$$$$\u003c/p\u003e\u003cp\u003eand\u003c/p\u003e\u003cp\u003e$$$$$$r \u003d \\max\\{((l\u0027 + lastans) \\bmod n) + 1, ((r\u0027 + lastans) \\bmod n) + 1\\}$$$$$$\u003c/p\u003e\u003cp\u003eshows me a new plan, where $$$\\min\\{x, y\\}$$$ and $$$\\max\\{x, y\\}$$$ correspond to the minimum and the maximum of $$$x$$$ and $$$y$$$ respectively, and that is what I execute this morning. You need to tell me the number you calculate for this day and I will set $$$lastans$$$ to your reply in modulo $$$(10^9 + 7)$$$.\u003c/p\u003e\u003cp\u003e\u0026nbsp; \u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input contains several test cases, and the first line contains a positive integer $$$T$$$ indicating the number of test cases which is up to $$$1000$$$.\u003c/p\u003e\u003cp\u003eFor each test case, the first line contains two integers $$$n$$$ and $$$m$$$ which are the number of food markets in the street and the total number of days I plan to spend in Ville Neuve respectively, where $$$1 \\le n, m \\le 10000$$$.\u003c/p\u003e\u003cp\u003eEach of the following $$$n$$$ lines describes a food market. The $$$i$$$-th line of them contains two integers $$$a_i$$$ and $$$b_i$$$ indicating the number of baguettes provided by the $$$i$$$-th food market and its unit price in euro respectively, where $$$1 \\le a_i, b_i \\le 1000$$$.\u003c/p\u003e\u003cp\u003eEach of the following $$$m$$$ lines contains three integers $$$l\u0027, r\u0027$$$ and $$$c$$$ describing the original plan I made for one day, where $$$1 \\le l\u0027 \\le r\u0027 \\le n$$$ and $$$1 \\le c \\le 1000$$$.\u003c/p\u003e\u003cp\u003eWe guarantee that no more than $$$10$$$ test cases satisfy $$$n \u0026gt; 100$$$ or $$$m \u0026gt; 100$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eCase #x:\u003c/span\u003e\" (without quotes) in a line at first, where \u003cspan class\u003d\"tex-font-style-tt\"\u003ex\u003c/span\u003e is the test case number starting from $$$1$$$.\u003c/p\u003e\u003cp\u003eThen for each day, output an integer in a line indicating the number of the different ways to purchase baguettes on this day in modulo the prime number $$$(10^9 + 7)$$$.\u003c/p\u003e"}},{"title":"Examples","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\u003e1\n3 3\n1 1\n1 2\n1 3\n1 3 1\n1 3 2\n1 3 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1:\n2\n3\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the sample case, I visit the first market and the second market with only one coin on the first day. Thus I can buy nothing or buy one baguette in the first shop. On the second day, I visit all markets carrying two coins, so I can buy nothing or buy one baguette in any one of the first two markets. On the last day, I visit the first two markets again but carry with me three coins. Then I have four different ways to purchase baguettes, but I am too tired to list them all after a three-day shopping.\u003c/p\u003e"}}]}