Сізге $n$ бос жиын $S_1,S_2,\dots ,S_n$ берілген. Екі түрлі сұрауды өңдеу қажет:

1. Сұрау түрі 1 l r x:

   • $l$-ден $r$-ге дейінгі (қоса алғанда) барлық жиындарға элемент $x$-ті қосу керек.

   • Басқаша айтқанда, әрбір $i$ үшін $l$-ден $r$-ге дейін: $$S_i\leftarrow S_i\cup \{x\}.$$

2. Сұрау түрі 2 l r:

   • $[l,r]$ кесіндісіндегі барлық жиындардың қиылысу мөлшерін есептеу қажет: $$\left|\bigcap _{i=l}^r{S}_i\right|.$$

   • $[l,r]$ кесіндісіндегі барлық жиындардың бірігу мөлшерін есептеу қажет: $$\left|\bigcup _{i=l}^r{S}_i\right|.$$

Осылайша, екінші түрдегі әрбір сұрау үшін екі санды шығару қажет: $$\left|\bigcap _{i=l}^r{S}_i\right|\text{және}\left|\bigcup _{i=l}^r{S}_i\right|.$$

Енгізу

Бірінші жолда екі бүтін сан $n$ және $q$ ($1\le n,q\le 100000$) берілген — жиындардың саны және сұраулардың саны сәйкесінше. Келесі $q$ жолында сұраулар сипатталған. Әрбір сұрау бір бүтін саннан $t$ басталады:

• Егер $t=1$, онда одан кейін үш бүтін сан $l$, $r$, $x$ беріледі, мұнда $1\le l\le r\le n$ және $1\le x\le n$.

• Егер $t=2$, онда одан кейін екі бүтін сан $l$, $r$ беріледі, мұнда $1\le l\le r\le n$.

Шығару

Әрбір сұрау үшін екі санды шығарыңыз — қиылысу мөлшері және кесіндідегі барлық жиындардың бірігу мөлшері.

Мысалдар

Енгізу 1

3 6
1 1 2 1
1 2 3 2
2 1 3
2 1 2
1 1 3 3
2 1 3

Жауап 1

0 2
1 2
1 3