Tobby is a very intelligent dog who loves to collect bones. In his house Tobby has a large shelf in which he stores his bones. The shelf is divided in N slots and each of those slots can hold at most one bone. The only difference between bones is their size, which is represented by an integer. Tobby is constantly buying new bones to fill his shelf and to replace other bones from his shelf. Tobby occasionally takes some of his bones for exhibitions around the country. Since Tobby is a lazy dog, he decides which bones to carry to an exhibition in the following way: he chooses two indexes i and j with i ≤ j and he carries to the exhibition all bones located between positions i and j of his shelf that have a size of at most S. Given a log of bones purchases and of exhibitions that Tobby needs to make between purchases, your task is to tell Tobby how many bones he should bring to each exhibition. Initially all the slots in Tobby’s shelf are empty. Input The input contains several test cases. Each test case begins with one line, in which there are two positive integers N (1 ≤ N ≤ 6∗105) and M (1 ≤ M ≤ 2∗106) that represent, respectively, the number of slots in Tobby’s shelf and the number of queries in the log. Then M lines follow, each containing a log entry. Each log entry starts with a number Q: • If Q is 0, then the log entry indicates that Tobby bought a bone. In that case two numbers follow: I (0 ≤ I ≤ N −1) and B (1 ≤ B ≤ 6∗105), indicating the index within the shelf in which the bone will be stored and the size of the bone. If there is already a bone stored in index I, then Tobby just replaces the bone in that index with the new bone. • If Q is 1, then the log entry indicates that Tobby wants to know how many bones he should bring to an exhibition. In that case three numbers follow: I, J (0 ≤ I ≤ J ≤ N − 1) and S (1 ≤ S ≤ 6∗105), indicating that Tobby wants to make an exhibition with all bones located between I and J (inclusive) of his shelf that have size less than or equal to S. Output For each exhibition query in the input, you should print a single line with the number of bones that Tobby should bring to that exhibition. Sample Input 5 10 005 016 027 1025 1026 035 046 1045 008 1047
2/2 Sample Output 1 2 2 4