All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
You are a tribal leader and live in jungle with your people. Life of the leader is not easy sometimes. One of your responsibilities is food distribution. Let's consider this process in details.
There are many families in your tribal. Thei-th family consists of Xipeople. In some moment you give each family Y bananas(Y is equal for all families independently of its size). All members of family receive equal number of bananas each and this number is maximal with condition that total number of bananas this family have received doesn't exceed Y. Of course some bananas of these initial Y are left. They are given back to the leader of the tribal(you). In other words each member of family receives floor Y / Xibananas and Y modulo Xi are given back to the leader.
. You are interested in total number of bananas you will have after this distribution process.
But things are not so simple. There are many events in life of your tribal. You will have to process many queries of three types:
- New family with Ximembers joined your tribal
- Some family with Ximembers left your tribal(it's guaranteed that there was such a family before this query).
- You give each family in your tribal Yj bananas. You want to know the total number of bananas you will have after distribution.
The first line of input file contains one integer N denoting number of different family sizes before queries. Each of next Nlines contains two space-separated integers Ai and Bi denoting size of the family and number of families with such size correspondingly. It's guaranteed that all the Ai are pairwise different.
The next line contains one integer M denoting the number of queries. Next M lines describe one query each and can be one of the three types:
- "+ X" - one family with X members joined your tribal
- "- X" - one family with X members left your tribal(it's guaranteed that there was such a family before this query).
- "? Y" - You give each family in your tribal Y bananas. You want to know the total number of bananas you will have after distribution.
For each third type query output one integer per line - answer for this query.
- 0 ≤ N ≤ 105
- 1 ≤ M ≤ 105
- 1 ≤ Ai, Bi, Xi, Yi≤ 105
Subtask #1[25 points]: M < 1000
Subtask #2[75 points]: no additional conditions
Input: 3 1 4 3 2 2 2 6 ? 10 ? 8 + 4 ? 9 - 2 ? 8 Output: 2 4 3 4
|Tags||ad-hoc, fenwick, ltime20, maths, medium-hard, pavel1996, segment-tree|
|Time Limit:||1 - 2.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.