380B орчуулах · Codeforces.mn

# Сережа ба Мод
Сережа моднуудыг шүтдэг. Өнөөдөр тэр эрс шинэчлэлт хийсэн хоёртын модтой (үндэс нь тэмдэглэгдсэн) учирсан.

Түүний шинэ мод нь $n$ давхаргатай ба орой бүр хоёр бүхэл тоон утгаар дугаарлагдана: давхаргын дугаар, тухайн давхарга дээр оройн байрлаж буй байрлалын дугаар. Модны үндэс нь $1$-р давхарга дээр байх ба үүний дугаар нь $(1, 1)$. Модны псеудо код нь:
    
    
      
    //the global data are integer arrays cnt[], left[][], right[][]  
      
    cnt[1] = 1;  
    fill arrays left[][], right[][] with values -1;  
    for(level = 1; level < n; level = level + 1){  
        cnt[level + 1] = 0;  
        for(position = 1; position <= cnt[level]; position = position + 1){  
            if(the value of position is a power of two){ // that is, 1, 2, 4, 8...  
                left[level][position] = cnt[level + 1] + 1;  
                right[level][position] = cnt[level + 1] + 2;  
                cnt[level + 1] = cnt[level + 1] + 2;              
            }else{  
                right[level][position] = cnt[level + 1] + 1;  
                cnt[level + 1] = cnt[level + 1] + 1;  
            }  
        }  
    }

Псеудо код ажилласаны дараа $cnt[level]$ массивын нүд нь $level$ давхаргын оройнуудын тоог агуулна. $left[level][position]$ массивын нүд нь $(level, position)$ дугаартай оройн зүүн хүүхдийн $level + 1$ давхарга дээрх дугаарыг агуулна эсвэл тухайн оройд зүүн хүүхэд байхгүй бол $-1$-г агуулна. Үүнтэй адилаар $right[level][position]$ массивын нүд нь баруун хүүхдийг илтгэнэ. Та тэмдэглэл хэсгээс $n = 4$ давхаргатай мод ямар байхын харж болно.

Сережа юмыг төвөгтэй болгох дуртай ба тэр эхлээд мод бүтээсэн ба орой бүр дээр $A(level, position)$ хоосон бүрдэл нэмсэн. Тэгээд Сережа $m$ ширхэг үйлдэл гүйцэтгэсэн. Үйлдэл бүр дараах хоёр төрлийн аль нэг нь байна:

* Үйлдлийн формат нь "$1$ $t$ $l$ $r$ $x$". Бүх $level, position$ $(level = t; l ≤ position ≤ r)$ оройн хувьд $x$ утгыг $A(level, position)$ бүрдэлрүү нэмнэ.
  * Үйлдлийн формат нь "$2$ $t$ $v$". $level, position$ оройн хувьд $(level, position)$ оройн дэд модны оройнуудын бүх бүрдлийн нэгдлийг олох. Уг бүрдлүүдийн нэгдлийн хэмжээг хэвлэх.

Сережад үйлдлүүдийг гүйцэтгэхэд туслана уу. Энэ бодлого дээр бүрдэл нь зөвхөн C++ дээрх std::set шиг ялгаатай утгуудыг агуулна.

## Оролт
Эхний мөрөнд $n$ ба $m$ $(1 ≤ n, m ≤ 7000)$ бүхэл тоон утгууд байна.

Дараагийн $m$ мөрөнд үйлдлүүдийн тодорхойлолтууд байна. Эхний төрлийн үйлдэл таван бүхэл тоон утгаар өгөгдөнө:  $1$ $t$ $l$ $r$ $x$ $(1 ≤ t ≤ n; 1 ≤ l ≤ r ≤ cnt[t]; 1 ≤ x ≤ 10^{6})$. Хоёр дахь төрлийн үйлдэл нь гурван бүхэл тоон утгаар өгөгдөнө: $2$ $t$ $v$ $(1 ≤ t ≤ n; 1 ≤ v ≤ cnt[t])$.

## Гаралт
Хоёр дахь төрлийн үйлдэл бүрийн хувьд хариултыг нэг мөрөнд хэвлэ.

## Тэмдэглэл
Та үндэстэй модтой ажиллах үедээ тодорхойломжуудыг дараах линкээс олж болно: http://en.wikipedia.org/wiki/Tree_(graph_theory)

Та $n = 4$ давхаргатай байгуулагдсан модыг доод зурагнаас харж болно.

![](http://codeforces.com/predownloaded/52/62/5262171b91129ac582cf5ef374695e5e7e9e10cb.png)

-- Г.Мэндбаяр

Жишээ тэстүүд

Оролт

Гаралт

2
0
1