— Willem... — What's the matter? — It seems that there's something wrong with Seniorious... — I'll have a look... Seniorious is made by linking special talismans in particular order. After over 500 years, the carillon is now in bad condition, so Willem decides to examine it thoroughly. Seniorious has n pieces of talisman. Willem puts them in a line, the i -th of which is an integer a i . In order to maintain it, Willem needs to perform m operations. There are four types of operations: 1 l r x : For each i such that l ≤ i ≤ r , assign a i + x to a i . 2 l r x : For each i such that l ≤ i ≤ r , assign x to a i . 3 l r x : Print the x -th smallest number in the index range l , r , i.e. the element at the x -th position if all the elements a i such that l ≤ i ≤ r are taken and sorted into an array of non-decreasing integers. It's guaranteed that 1 ≤ x ≤ r - l + 1 . 4 l r x y : Print the sum of the x -th power of a i such that l ≤ i ≤ r , modulo y , i.e. . The only line contains four integers n , m , seed , v max ( 1 ≤ n , m ≤ 10 5 , 0 ≤ seed < 10 9 + 7, 1 ≤ vmax ≤ 10 9 ). The initial values and operations are generated using following pseudo code: Here op is the type of the operation mentioned in the legend. For each operation of types 3 or 4 , output a line containing the answer. In the first example, the initial array is {8, 9, 7, 2, 3, 1, 5, 6, 4, 8} . The operations are: 2 6 7 9 1 3 10 8 4 4 6 2 4 1 4 5 8 2 1 7 1 4 7 9 4 4 1 2 7 9 4 5 8 1 1 2 5 7 5 4 3 10 8 5