Програмчлалын олимпиадын бодлогын архив

1 -> N (N <= 1000000) тооны 2 сэлгэмэл өгөгдөнө. 1 -> N тооны сэлгэмэл гэдэг нь яг N ширхэг тоо байх ба 1 -> N хоорондох бүх тоо тус бүр яг нэг удаа орсон байх жагсаалт буюу массивыг хэлнэ. Эхний сэлгэмэлийг А, хоёр дахь сэлгэмэлийг В гэе. Q (Q <= 1000000) ширхэг асуулга буюу хүсэлт ирнэ. Хүсэлт тус бүр нь L1, R1, L2, R2 (1 <= L1 <= R1 <= N ба 1 <= L2 <= R2 <= N энэ нөхцөлийг хангах) гэсэн 4 ширхэг тоо өгөгдөнө. A[L1] --> A[R1] завсар дахь тоонуудыг S1 гэе. B[L2] --> B[R2] завсар дахь тоонуудыг S2 гэе. S1  ба S2 олонлогын огтлолцол буюу давхцаж байгаа тоонуудыг S3 гэж үзвэл Хүсэлт тус бүрийн хариулт нь |S3| буюу S3 олонлогийн элементийн тоо байна. Та хүсэлт тус бүр дахь тоог тус бүрт нь нэг нэг мөрөнд хэвлэхэд л хангалттай.
Input

N, Q

1 --> N тооны сэлгэмэл буюу А.

Output

A сэлгэмэлийн L1 дахь элементээс R1 дахь элемент хүртэлх (L1, R1 дахь элементүүд мөн өөрсдөө орно) элементүүд болон B сэлгэмэлийн L2 дахь элементээс R2 дахь элемент хүртэлх (L2, R2 дахь элементүүд мөн өөрсдөө орно) элементүүдийн огтлолцол буюу давхцаж байгаа элементийн тоог хэвлэнэ

Эхний жишээг тайлбарлая А сэлгэмэл нь 3 5 2 1 4 гэсэн таван элементээс бүрдэж байна. В сэлгэмэл нь 2 1 4 5 3 гэсэн мөн таван элементээс бүрдэж байна. Эхний хүсэлт буюу асуулга 2 4 1 3 гэсэн дөрвөн тооноос бүрдэж байна. Энэ нь А сэлгэмэлийн 2 дахь элементээс 4 дахь элемент хүртэлх тоонуудыг (эдгээр тоонууд нь 5 2 1 байна) S1 гэе. В сэлгэмэлийн 1 дахь элементээс 3 дахь элемент хүртэлх тоонуудыг (эдгээр тоонууд нь 2 1 4 байна) S2 гэе. S1, S2 олонлогийн огтлолцол буюу давхцаж байгаа элементүүд нь 2 1 байна. Энэ огтлолцсон олонлогийн элементийн нийт тоо 2 ширхэг учраас Эхний гаралт 2 байна. Хоёр дахь гаралт нь 1 байна. Энэ нь А олонлогоос 2 1 4, В олонлогоос 4 5 3 гэсэн хоёр олонлогийн огтлолцол нь 4 гэсэн нэг элементтэй олонлог үүсч байгаа учраас элементийн тоо нь 1 байна.

Example

Input:

5 2

3 5 2 1 4

2 1 4 5 3

2 4 1 3

3 5 3 5

Output:

2

1