{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/MARCH14/mandarin/STREETTA.pdf\"\u003eMandarin Chinese \u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/MARCH14/russian/STREETTA.pdf\"\u003eRussian\u003c/a\u003e.\u003c/h3\u003e\r\n\u003cp\u003eThe String street is known as the busiest street in Codeland.\r\nTourists from all over the world want to visit the street once they are in Codeland.\r\nThe Chef owns \u003cb\u003eN\u003c/b\u003e souvenir stores across the street (numbered from \u003cb\u003e1\u003c/b\u003e to \u003cb\u003eN\u003c/b\u003e). \r\nAt the beginning there is no souvenir in any store, the Chef has some plans to add some new items.\r\nEach the Chef\u0027s plan is represented by 4 numbers: \u003cb\u003eu v a b\u003c/b\u003e which mean an items with price \u003cb\u003eb\u003c/b\u003e \r\nis added to the store \u003cb\u003eu\u003c/b\u003e, an items with price \u003cb\u003ea + b\u003c/b\u003e is added to the store \u003cb\u003eu + 1\u003c/b\u003e and so on. \r\nMore formally, an item with price \u003cb\u003ea * i + b\u003c/b\u003e is added to the store \u003cb\u003eu + i\u003c/b\u003e for all (\u003cb\u003e0 ≤ i ≤ v - u\u003c/b\u003e).\u003c/p\u003e\r\n\u003cp\u003eIn additional to the cost of the item itself, the tourist must pay some conservation fees as well.\r\nThe Codeland regularly defines the new conservation fee. Each fee is represented by 4 numbers: \u003cb\u003eu v a b\u003c/b\u003e which means\r\nthe tourist buying any item in the store \u003cb\u003eu + i\u003c/b\u003e will be charged a fee of \u003cb\u003ei * a + b\u003c/b\u003e for all (\u003cb\u003e0 ≤ i ≤ v - u\u003c/b\u003e).\r\nIn the case that several conservation fees have effect on the same store, the customer needs to pay all of those fees.\u003c/p\u003e\r\n\u003cp\u003eAt some point of time, a tourist at store \u003cb\u003ei\u003c/b\u003e asks you what is the \u003cb\u003elargest\u003c/b\u003e amount of money they have to spend for \r\na souvenir at that store (the amount of money includes the price of one of the souvenirs and all the conservation fees for that store).\u003c/p\u003e\r\n\r\n\u003cp\u003e \u003c/p\u003e\r\n\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eThe first line of the input contains two integers \u003cb\u003eN\u003c/b\u003e and \u003cb\u003eM\u003c/b\u003e represent the number of stores and the number of events\u003c/li\u003e\r\n\u003cli\u003eEach of the next \u003cb\u003eM\u003c/b\u003e lines represents an event of three types below in the chronological order.\r\n\t\u003cul\u003e\r\n\t\u003cli\u003eThe new plan of the Chef: \"1 \u003cb\u003eu v a b\u003c/b\u003e\".\u003c/li\u003e\r\n\t\u003cli\u003eThe new conservation fee: \"2 \u003cb\u003eu v a b\u003c/b\u003e\".\u003c/li\u003e\r\n\t\u003cli\u003eThe query from tourist: \"3 \u003cb\u003ei\u003c/b\u003e\".\u003c/li\u003e\r\n\t\u003c/ul\u003e\r\n\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003e \u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each query from tourist, print in one line the corresponding answer.\r\nIf there is no item at the \u003cb\u003ei\u003c/b\u003eth store, print out \"NA\" (without quotes) as the answer.\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e9\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eM\u003c/b\u003e ≤ \u003cb\u003e3*10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003eFor events of type 1: \u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eu\u003c/b\u003e ≤ \u003cb\u003ev\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e. \u003cb\u003e|a|, |b| ≤ 10\u003csup\u003e9\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003eFor events of type 2: \u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eu\u003c/b\u003e ≤ \u003cb\u003ev\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e. \u003cb\u003e|a|, |b| ≤ 10\u003csup\u003e4\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003eFor events of type 3: \u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003ei\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e \u003c/p\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003e \u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\r\n10 10\r\n3 5\r\n1 3 8 3 1\r\n3 5\r\n1 5 10 -8 2\r\n3 5\r\n3 10\r\n2 1 10 0 1\r\n3 6\r\n2 5 7 2 1\r\n3 6\r\n\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\nNA\r\n7\r\n7\r\n-38\r\n11\r\n14\r\n\u003c/pre\u003e\r\n\u003ch3\u003eExplanation\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\r\nAt the beginning all stores are empty so the answer for the first query which asks about the store 5 is \"NA\".\r\n\u003c/li\u003e\r\n\r\n\u003cli\u003e\r\nThe first plan of the Chef is \"3 8 3 1\" which means the items with price 1, 4, 7, 10, 13, 16 are added to the stores 3, 4, 5, ..., 8 correspondingly. So in the next query (asking about store 5) the answer is 7 (we have only one item to buy with no conservation fee).\r\n\u003c/li\u003e\r\n\r\n\u003cli\u003e\r\nThe second plan of the Chef is \"5 10 -8 2\" so the items with price 2, -6, -14, -22, -30, -38 are added to the stores 5, 6, 7, ..., 10 correspondingly. Now the store 5 now contains two items with the corresponding prices are 7 and 2, the answer for the query about store 5 is still 7 (we still don\u0027t have any conservation fee). The store 10 contain only one item with price is -38 so the answer for the query about this store is -38.\r\n\u003c/li\u003e\r\n\u003cli\u003e\r\nThe first conservation fee policy is \"1 10 0 1\" which cause a conservation fee of 1 for each of 10 stores. The stores 6 contains 2 items, one costs 10 unit of money and the other costs -6. We need to pay 1 unit of money for the conservation fee so the largest amount of money we can spend for one item in store 6 is 10 + 1 \u003d 11.\r\n\u003c/li\u003e\r\n\u003cli\u003e\r\nThe second conservation fee policy is \"5 7 2 1\" so a conservation fees of 1, 3, 5 are added to the stores 5, 6 and 7 correspondingly. Hence the largest amount of money we can spend for one item in store 6 is increased by 3. The answer for the last query is 14.\r\n\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003e\u003cb\u003eNote: \u003c/b\u003eBoth of the price and the conservation fee can be negative.\u003c/p\u003e"}}]}