Cuộc đua nhiệm vụ

Ngày xửa ngày xưa, trong vương quốc Kỳ Diệu, nhà vua tổ chức một cuộc thi dành cho những chiến binh dũng cảm và thông minh nhất. Nhà vua giao cho các chiến binh một danh sách gồm \(N\) nhiệm vụ để thực hiện, mỗi nhiệm vụ chỉ được hoàn thành khi chiến binh bắt đầu tác vụ từ thời điểm \(l_i\) và hoàn thành tại thời điểm \(r_i\).

Vì độ khó của các nhiệm vụ, các chiến binh không thể đồng thời thực hiện nhiều tác vụ cùng một thời điểm, hay cụ thể là hai nhiệm vụ giao nhau. Hai nhiệm vụ \([l_i, r_i]\) và \([l_j, r_j]\) được gọi là giao nhau nếu tồn tại một thời điểm thuộc cả \(2\) nhiệm vụ trên.

Cuộc thi trên không chỉ là cơ hội tìm kiếm chiến binh mạnh nhất, mà còn là cơ hội để những người "mạnh" về trí não thể hiện khả năng. Cụ thể, nhà vua giao ra bài toán sau, nếu một chiến binh chỉ được làm các nhiệm vụ trong khoảng thời gian từ \(S\) đến \(T\) thì họ có thể hoàn thành tối đa bao nhiêu nhiệm vụ. Nhận thấy bài toán chưa đủ hóc búa, nhà vua bèn chèn thêm một số cập nhật giữa các câu hỏi: thay đổi thời gian của nhiệm vụ \(i\) thành \(U_i\) đến \(V_i\).

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \leq N \leq 10^5)\), là số lượng nhiệm vụ.

• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i\) và \(r_i\) \((1 \leq l_i \le r_i \leq 10^9)\), biểu diễn thời gian bắt đầu và kết thúc của nhiệm vụ thứ \(i\).

• Dòng tiếp theo chứa số nguyên \(Q\) (\(1 \le Q \le 10^5\)), là số lượng yêu cầu mà nhà vua đưa ra.

• Q dòng tiếp theo thuộc một trong \(2\) loại:
  \begin itemize

• \(1 \; i \; u \; v\): Gán \(l_i=u\) và \(r_i=v\).
• \(2 \; S \; T\): Nếu chỉ được phép làm nhiệm vụ trong khoảng thời gian \([S, T]\), thì một chiến binh có thể làm nhiều nhất bao nhiêu nhiệm vụ.
  \end itemize

Output

Xử lý các yêu cầu và đưa ra đáp án cho các câu hỏi của nhà vua.

Example

5
1 5
3 7
2 4
7 10
6 11
4
2 3 10
2 2 10
1 2 11 13
2 1 14

1
2
3

Scoring

Trong tất cả các test:

\(1 \le u \le v \le 10^9\)

\(1 \le S \le T \le 10^9\)

\textbf Cách tính điểm:
\begin itemize

• Có \(15\%\) số điểm ứng với \(n, q \le 20\).
• Có \(15\%\) số điểm ứng với \(n, q \le 10^3\).
• Có \(20\%\) số điểm ứng với \(l_i = r_i\) và \(u = v\).
• Có \(20\%\) số điểm với bộ test không có truy vấn loại \(1\).
• \(30\%\) điểm còn lại không có ràng buộc gì thêm.
  \end itemize