Познати продавац магле Џони Фог је одлучио да свој бизнис прошири у једном од највећих градова на свету - Нишу, јер је чуо да се тамо од продаје магле баш лепо живи. Познато је да је Ниш организован као Њујорк тј. састоји се од \(m\) паралелних хоризонталних авенија и \(m\) паралелних вертикалних булевара у чијем се пресеку налази \(m^2\) раскрсница; означимо раскрсницу у пресеку \(i\)-те авеније и \(j\)-тог булевара са \((i,j)\). Како су растојања између суседних авенија и суседних булевара једнака \(1\) km, јасно је да је растојање између раскрсница \((a,b)\) и \((c,d)\) једнако \(|a-c| + |b-d|\) km. Џони планира да отвори киоске магле на неким раскрсницама и да продаје маглу на кило.

Међутим, продавцима магле није лако - уколико се нпр. појаве представници закона, Џони мора да хвата маглу и преноси је из свих својих киоска на неко сигурно место. Познато је да је за пренос једног килограма магле на растојању од 1 километар потребан 1 минут. Помозите Џонију да испланира своје време тако што ћете симулирати \(n\) упита неког од следећа два типа:

• \(1\) \(x\) \(y\) \(v\) - Џони отвара нови киоск са \(v\) килограма магле на раскрсници \((x,y)\);
• \(2\) \(x\) \(y\) - Џонија занима колико би му минута требало да пренесе маглу из свих тренутно отворених киоска на раскрсницу \((x,y)\).

Уколико помогнете Џонију, добијате 5кг магле!

Опис улаза

У првом реду стандардног улаза налазе се два природна броја \(n\) и \(m\), број упита и број авенија/булевара, редом. У наредних \(n\) редова налазе се одговарајући упити: или 4 природна броја \(1\) \(x_i\) \(y_i\) \(v_i\) (уколико је у питању упит типа 1) или 3 природна броја \(2\) \(x_i\) \(y_i\) (уколико је у питању упит типа 2) чије је значење дато у опису упита.

Опис излаза

За сваки упит типа 2 исписати, у посебном реду и одговарајућем редоследу, један природан број - одговор на тај упит.

Примери

Пример 1

Улаз

5 20
1 3 7 10
1 2 2 8
2 5 3
1 10 10 3
2 1 1

Излаз

92
150

Пример 2

Улаз

2 1000000000
1 1 1 10000
2 1000000000 1000000000

Излаз

19999999980000

Објашњење примера

У првом тест примеру, прво се отвори киоск 10кг магле на раскрсници \((3, 7)\), затим се отвара киоск са 8кг магле на раскрсници \((2, 2)\). За следећи упит, треба израчунати време пребацивања магле из ова два киоска на раскрсницу \((5, 3)\). Растојање између раскрсница \((3, 7)\) и \((5, 3)\) је \(|5-3| + |3-7| = 6\), растојање између раскрсница \((2, 2)\) и \((5, 3)\) је \(4\), па је за овај подухват потребно \(10 \cdot 6 + 8 \cdot 4 = 92\) минута. У следећем упиту се отвара киоск са 3кг магле на раскрсници \((10, 10)\). У последњем упиту треба израчунати време пребацивања магле из отворена 3 киоска на раскрсницу \((1,1)\) што је \(80 + 16 + 54 = 150\) минута.

Ограничења

• \(2 \leq n \leq 250.000\)
• \(1 \leq m \leq 10^9\)
• \(1 \leq x_i, y_i \leq m\)
• \(1 \leq v_i \leq 10^4\)
• Могуће је да се више различитих продавница отвори на истој раскрсници

Тест примери су подељени у пет дисјунктних група: * У тест примерима који вреде \(10\) поена важиће \(n \leq 5.000\). * У тест примерима који вреде \(20\) поена важиће \(n \leq 150.000\) и \(m \leq 10^3\). * У тест примерима који вреде \(20\) поена сви упити типа 1 биће пре свих упита типа 2. * У тест примерима који вреде \(25\) поена важиће \(m \leq 300.000\). * У тест примерима који вреде \(25\) поена нема додатних ограничења.