Magical Number

Problem description
Mojo loves to play with nonnegative 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 NonMagical 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 NonMagical numbers in same range.
2.Update the disturbed collection at index “i” if number at index “i” is NonMagical. If number is NonMagical prime, then it must be replaced with Magical prime just greater than that NonMagical prime and less than or equal to "N". If no such number exists, replace the NonMagical prime with greatest Magical Prime less than or equal to “N”.
Similarly, if the number is Nonmagical Non prime, then it must be replaced with Magical Non prime just greater than that NonMagical Non prime and less than or equal to "N". If no such number exists, replace the NonMagical 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 NonMagical numbers.
Note: Queries on Disturbed collection are 1indexed.
.
Input
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.)
Output
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.
Constraints
 1 ≤ N ≤ 10^6
 1 ≤ Q ≤ 10^5
 type={1,2}
 1 ≤ L ≤ R ≤ N+1
 1 ≤ T ≤ 10
Example
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
Explanation
Case 1:
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:
0,1,2,3,4,5,6,7,8,9,10,12,21
whereas all other numbers are NonMagical.
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 nonMagical 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.
Author:  dwij28 
Tags  dwij28 
Date Added:  19042017 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions