Mojo loves to play with non-negative numbers. One day, he discovered a number in which every digit is either 1 greater than its just left neighbour or 1 less than its just left neighbour, and also every digit is either 1 greater than its just right neighbour or 1 less than its just right neighbour.
If only one of the neighbour digits exists, then either just left side or just right side neighbour should be 1 greater or 1 less. Mojo calls such group of numbers as “Magical Numbers”. All single digit numbers also falls into this category.
For example : 0, 2 , 6 , 12, 121, 989, 3212 etc.
One day his naughty friend Dodo visited his house. He saw the collection of all Magical numbers in his house. Being curios in nature, he started thinking about those numbers (since he didn’t know about Magical Numbers).After thinking a lot, he took a number “N” just greater than or equal to the maximum number in that collection of Magical Numbers and hence added all those non negative numbers till “N” which were not present in that collection. And then arranged all the numbers in increasing order. Here “N” can be any number greater than or equal to maximum Magical Number of Mojo’s collection.
After seeing that his collection of Magical numbers had disturbed, Mojo became angry on Dodo and asked him to replace Non-Magical numbers with the Magical numbers initially he had.
Hence, Mojo gave “Q” queries to Dodo of following type:
1. Find the count of all Magical numbers within a given range [L,R].Also find the sum of all Magical as well as Non-Magical numbers in same range.
2.Update the disturbed collection at index “i” if number at index “i” is Non-Magical. If number is Non-Magical prime, then it must be replaced with Magical prime just greater than that Non-Magical prime and less than or equal to "N". If no such number exists, replace the Non-Magical prime with greatest Magical Prime less than or equal to “N”.
Similarly, if the number is Non-magical Non prime, then it must be replaced with Magical Non prime just greater than that Non-Magical Non prime and less than or equal to "N". If no such number exists, replace the Non-Magical Non prime with greatest Magical Non Prime less than or equal to “N”.
After all the queries, Mojo will become happy with dodo, if Magical Numbers in entire collection is greater than Non-Magical numbers.
Note: Queries on Disturbed collection are 1-indexed. .
First line contains an integer “T” denoting number of test cases.
First line of each test case contains two space separated integers “N” and “Q”, denoting the number selected by Dodo and the number of queries. Next Q lines consists of queries of following form :
- 1 L R: (1 is type and L and R as described above)
- 2 i: (2 is type and “i” is index to be updated as described above.)
In each test case, for query of type 1, output two space separated integers as described above, in a new line. After all the queries, output “happy”(without quotes) if Mojo is happy else output “unhappy”(without quotes) in a new line.
- 1 ≤ N ≤ 10^6
- 1 ≤ Q ≤ 10^5
- 1 ≤ L ≤ R ≤ N+1
- 1 ≤ T ≤ 10
Input: 2 21 5 1 4 10 2 10 1 5 13 2 12 1 9 22 25 4 2 13 2 18 2 25 1 1 25 Output: 7 42 8 72 6 199 happy 16 303 happy
Dodo took a number "21".Hence in Mojo's collection the maximum Magical number must be just less than or equal to 21.So, it must be 21 itself.
Now the disturbed collection contains : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21.
Thus Mojo's collection of Magical Numbers must had been as follows:
whereas all other numbers are Non-Magical.
Query 1: Count=7(3,4,5,6,7,8,9) Sum=42 (3+4+5+6+7+8+9)
Query 2: Index 10 has value 9 which is already a "Magical Number", so no update needed.
Query 3: Count=8(4,5,6,7,8,9,10,12) Sum=(4+5+6+7+8+9+10+11+12)
Query 4: Index 12 has value 11 which is non-Magical Prime.Since there are no Magical Prime just greater than 11 and less than 21.Hence index 12 is updated with maximum Magical Prime less than or equal to 21 ie 7.
Query 5: Count=6(8,9,10,7,12,21) Sum=199(8+9+10+7+12+13+14+15+16+17+18+19+20+21)
Now out of 22 numbers in Collection, 14 numbers are Magical.Hence Mojo become happy.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions