Willem, Chtholly and Seniorious

— Willem...

— 무슨 일이야?

— Seniorious에 뭔가 문제가 생긴 것 같아...

— 내가 살펴볼게...

Seniorious는 특별한 부적들을 특정한 순서로 연결하여 만들어진다.

500년이 넘는 세월이 흐른 뒤, 이 카리용은 현재 상태가 좋지 않으므로 Willem은 이를 철저히 점검하기로 한다.

Seniorious에는 n개의 부적 조각이 있다. Willem은 이들을 한 줄로 놓으며, 그중 i-th은 정수 ai이다.

이를 유지 보수하기 위해 Willem은 m개의 연산을 수행해야 한다.

연산에는 네 가지 유형이 있다:

• 1 l r x: l ≤ i ≤ r를 만족하는 각 i에 대해, ai에 ai + x를 대입한다.
• 2 l r x: l ≤ i ≤ r를 만족하는 각 i에 대해, ai에 x를 대입한다.
• 3 l r x: 인덱스 범위 [l, r]에서 x-th번째로 작은 수를 출력한다. 즉, l ≤ i ≤ r를 만족하는 모든 원소 ai를 가져와 비내림차순 정수 배열로 정렬했을 때 x-th 위치에 있는 원소를 출력한다. 1 ≤ x ≤ r - l + 1임이 보장된다.
• 4 l r x y: l ≤ i ≤ r를 만족하는 ai의 x-th제곱의 합을 y로 나눈 나머지, 즉 를 출력한다.

유일한 줄에 네 정수 n, m, seed, vmax (1 ≤ n, m ≤ 105, 0 ≤ seed < 109 + 7, 1 ≤ vmax ≤ 109)가 주어진다.

초깃값과 연산은 다음 의사 코드로 생성된다:

def rnd():  
  
    ret = seed  
    seed = (seed * 7 + 13) mod 1000000007  
    return ret  
  
for i = 1 to n:  
  
    a[i] = (rnd() mod vmax) + 1  
  
for i = 1 to m:  
  
    op = (rnd() mod 4) + 1  
    l = (rnd() mod n) + 1  
    r = (rnd() mod n) + 1  
  
    if (l > r):   
         swap(l, r)  
  
    if (op == 3):  
        x = (rnd() mod (r - l + 1)) + 1  
    else:  
        x = (rnd() mod vmax) + 1  
  
    if (op == 4):  
        y = (rnd() mod vmax) + 1  
  

여기서 op는 위 설명에서 언급한 연산의 유형이다.

유형 3 또는 4의 각 연산에 대해, 정답을 담은 한 줄을 출력한다.

첫 번째 예제에서 초기 배열은 {8, 9, 7, 2, 3, 1, 5, 6, 4, 8}이다.

연산은 다음과 같다:

• 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