F. Лена ба асуултууд

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Лена программист бөгөөд тэрээр ажил дээрээ нэгэн даалгавар гүйцэтгэхээр болжээ.

Түүнд хос бүхэл тоонуудын хоосон олонлог болон гүйцэтгэх ёстой $n$ ширхэг асуултууд байв. Асуулт болгон нь дараах 3-н төрлийн аль нэг нь байх ажээ:

  1. $(a, b)$ гэсэн хосыг уг олонлог уруу нэмж оруулна.
  2. $i$ гэсэн дугаартай асуулт дээр уг олонлог уруу нэмж оруулсан хосыг уг олонлогоос хасна. Түүнчлэн бүх асуултууд нь $1$-ээс $n$ хүртэлх бүхэл тоонуудаар дугаарлагдсан байх юм.
  3. Өгөгдсөн $q$ бүхэл тооны хувьд уг олонлог доторх бүх $(x, y)$ хосууд дундаас $x*q + y$-ын хамгийн их утгыг олно.

Лена-д туслан эдгээр асуултуудыг гүйцэтгэж өгнө үү.

Оролт

Эхний мөрөнд асуултуудын тоог илэрхийлэх бүхэл тоо $n$ ($1 ≤ n ≤ 3*10^{5}$) өгөгдөнө.

Дараагийн $n$ мөрийн мөр болгоны эхэнд асуултын төрлийг илэрхийлэх бүхэл тоо $t$ ($1 ≤ t ≤ 3$) өгөгдөнө.

Эхний төрлийн асуултын хувьд $t$ тооны араас хос бүхэл тоо $a$ болон $b$ ($ - 10^{9} ≤ a, b ≤ 10^{9}$) өгөгдөнө.

2-р төрлийн асуултын хувьд $t$ тооны араас бүхэл тоо $i$ ($1 ≤ i ≤ n$) өгөгдөх ба $i$ нь уг асуултын дугаараас бага байх юм. Түүнчлэн $i$ гэсэн дугаартай асуулт нь эхний төрлийн асуулт байх бөгөөд $i$-р асуулт дээр уг олонлог уруу нэмж оруулсан хос нь уг олонлог дотроос хараахан хасагдаагүй байна.

3-р төрлийн асуултын хувьд $t$ тооны араас бүхэл тоо $q$ ($ - 10^{9} ≤ q ≤ 10^{9}$) өгөгдөнө.

Гаралт

3-р төрлийн асуулт бүрийн хувьд тусдаа мөрөнд $x*q + y$-ын хамгийн их утгыг хэвлэнэ үү.

Хэрэв хариултыг хэвлэх үед тухайн олонлог дотор нь ямар ч хос байхгүй бол "EMPTY SET" гэж хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
7
3 1
1 2 3
3 1
1 -1 100
3 1
2 4
3 1
Гаралт
EMPTY SET
5
99
5
Сэтгэгдлүүдийг ачааллаж байна...