Bob's math is really poor. He even doesn't know how does `carry' works in plus operation. In his world, the `plus' operation performed like this : 9+5=4{9+5=4}9+5=4, 99+99=88{99+99=88}99+99=88, 5876+5576=342{5876+5576=342}5876+5576=342, 5555+5555=0{5555+5555=0}5555+5555=0, 1503+2503=3006{1503+2503=3006}1503+2503=3006, 512+1314=1826{512 + 1314 = 1826}512+1314=1826. Oh how poor his math is and he could even be the problem setter. Tragedy. In his world, there is a `Wish' data structure. Let's see how it works: [*.] Initially, there will be a list of numbers to initialize the data structure. After initialization, game begins: [1.] You may add a number to his data structure. AddxAdd xAddx [2.] You may divide all the numbers in the data structure by 10{10}10. ShiftShift Shift [3.] You may query the largest result by given x{x}x `plus' any number from his data structure. QueryxQuery xQueryx [4.] You may query `sum' of numbers between L{L}L and R{R}R inclusive. It means, you need to find all numbers x{x}x in his data structure that can meet L≤x≤RL leq x leq RL≤x≤R, and conduct the `plus' one by one to get the `sum'. SumLRSum L RSumLR Can you help naive Bob to implement data struct `Wish'?
Bob's math is really poor. He even doesn't know how does `carry' works in plus operation. In his world, the `plus' operation performed like this : 9+5=4{9+5=4}9+5=4, 99+99=88{99+99=88}99+99=88, 5876+5576=342{5876+5576=342}5876+5576=342, 5555+5555=0{5555+5555=0}5555+5555=0, 1503+2503=3006{1503+2503=3006}1503+2503=3006, 512+1314=1826{512 + 1314 = 1826}512+1314=1826. Oh how poor his math is and he could even be the problem setter. Tragedy. In his world, there is a `Wish' data structure. Let's see how it works: [*.] Initially, there will be a list of numbers to initialize the data structure. After initialization, game begins: [1.] You may add a number to his data structure. Add xAdd xAdd x [2.] You may divide all the numbers in the data structure by 10{10}10. (Note: it is integer division, for example, 9/10=0{9 / 10 = 0}9/10=0, 99/10=9{99 / 10 = 9}99/10=9, 5876/10=587{5876 / 10 = 587}5876/10=587) Shift Shift Shift [3.] You may query the largest result by given x{x}x `plus' any number from his data structure. Query xQuery xQuery x [4.] You may query `sum' ( by his poor math ) of numbers between L{L}L and R{R}R inclusive. It means, you need to find all numbers x{x}x in his data structure that can meet L≤x≤RL leq x leq RL≤x≤R, and conduct the `plus' one by one to get the `sum'. Sum L RSum L RSum L R Can you help naive Bob to implement data struct `Wish'?
