28ος ΠΔΠ Καμπ (κοινά)
Ποδηλάτες (bicycle)

Ο Δήμαρχος αποφάσισε να κατασκευάσει ένα πάρκινγκ ποδηλάτων σε κάποια θέση κατά μήκος του ποταμού. Λόγω του ισχυρού ανέμου, οι ποδηλάτες που κινούνται προς τα δεξιά μπορεί να δυσκολευτούν περισσότερο (ή λιγότερο) από τους ποδηλάτες που κινούνται προς τα αριστερά για να φτάσουν στο πάρκινγκ. Συγκεκριμένα, για δοθέντες ακεραίους \(a\), \(b\), που εξαρτώνται αποκλειστικά από τον άνεμο, η δυσκολία του κάθε ποδηλάτη που βρίσκεται αριστερά του πάρκινγκ είναι η απόστασή του από το πάρκινγκ, πολλαπλασιασμένη με τη σταθερά \(a\), ενώ η δυσκολία του κάθε ποδηλάτη που βρίσκεται δεξιά του πάρκινγκ είναι η απόστασή του από το πάρκινγκ πολλαπλασιασμένη με τη σταθερά \(b\). Ο Δήμαρχος θέλει να τοποθετήσει το πάρκινγκ έτσι ώστε να ελαχιστοποιήσει τη συνολική δυσκολία, που είναι ίση με το άθροισμα των επιμέρους δυσκολιών όλων των ποδηλατών.

Επειδή ο Δήμαρχος δεν γνωρίζει ακριβώς τις θέσεις των ποδηλατών, αλλά ούτε και τις συνθήκες του ανέμου, δοκιμάζει διάφορα σενάρια για την τοποθέτηση. Δίνονται \(Q\) ερωτήματα, τριών διαφορετικών ειδών:

\(1\) \(x\): Εισαγωγή ενός νέου ποδηλάτη στη θέση \(x\) κατά μήκος του ποταμού, όπου \(x\) θετικός φυσικός.
\(2\) \(x\): Αφαίρεση ενός ποδηλάτη από τη θέση \(x\) κατά μήκος του ποταμού. Σημειώνεται ότι πριν την αφαίρεση θα υπάρχει τουλάχιστον ένας ποδηλάτης στη θέση \(x\).
\(3\) \(a\) \(b\): Υπολογισμός της ελάχιστης δυνατής συνολικής δυσκολίας, αν το πάρκινγκ τοποθετηθεί στην καλύτερη δυνατή θέση, δεδομένου ότι οι σταθερές ανέμου είναι οι φυσικοί αριθμοί \(a\) και \(b\).

Γράψτε ένα πρόγραμμα που να διαβάζει αυτά τα δεδομένα και για κάθε ερώτημα τύπου \(3\) να βρίσκει την ελάχιστη συνολική δυσκολία. Θεωρήστε ότι σε κάθε θέση μπορεί να υπάρχει και πάνω από ένας ποδηλάτης.

Αρχεία Εισόδου (bicycle.in):

Η πρώτη γραμμή της εισόδου θα περιέχει έναν φυσικό αριθμό \(Q\): το συνολικό πλήθος των ερωτημάτων που θα ακολουθήσουν. Κάθε μία από τις επόμενες \(Q\) γραμμές αντιστοιχεί σε ένα ερώτημα. Κάθε γραμμή μπορεί να έχει μία από τις μορφές «\(1\) \(x\)», «\(2\) \(x\)», και «\(3\) \(a\) \(b\)», όπου \(x\), \(a\), \(b\) θετικοί φυσικοί.

Αρχεία Εξόδου (bicycle.out):

Η έξοδος πρέπει να αποτελείται από τόσες γραμμές, όσα είναι και τα ερωτήματα τύπου \(3\) στην είσοδο και κάθε μία από αυτές τις γραμμές να περιέχει ένα φυσικό αριθμό, την απάντηση στο αντίστοιχο ερώτημα τύπου \(3\).

Παράδειγμα Αρχείου Εισόδου - Εξόδου:

bicycle.in	bicycle.out
8 1 1 1 2 1 3 3 1 1 2 2 1 4 1 5 3 3 1	2 9

Εξήγηση παραδείγματος: Στην πρώτη περίπτωση το πάρκινγκ θα τοποθετηθεί στη θέση \(2\), ενώ στη δεύτερη μπορεί να τοποθετηθεί είτε στη θέση \(1\) είτε στη θέση \(3\).

Subtasks

Σε τουλάχιστον 70% των παραδειγμάτων εισόδου θα ισχύει ότι \(x \leq 100.000\).

Περιορισμοί