**Chef and Queries ( add a number in to set , delete anumber form set and , finally print sum in the set)

Chef and Queries

As part of his daily job, Chef has to solve problems involving sets. Till now, Chef has been using inefficient methods to solve his set related problem, wasting a lot of his precious time. He has agreed to pay you a lot of money for solving the following problem for him efficiently.

First, Chef needs to perform Q operations on a set. Each operation is either:

• 1. Add a number to the set (if this number is NOT already present in the set).
• 2. Erase a number from the set (if this number exists in the set).
  • 1 ≤ Q ≤ 10⁷
  • 1 ≤ S₁, A, B ≤ 10⁹
Then, he needs to find the sum of all elements of the set after performing these Q queries. Your job is to find this sum for him quickly.

Input

The first line of input contains four integers — Q, S₁, A, B. S₁ is the first number in the operations. Aand B are special constants explained later.
Every operation S_i is represented by a single integer. If S_i is odd, then it represents the first operation, otherwise the second type, and in both of them the integer you have to add/delete equals [S_i / 2], where [] is the greatest integer (or floor) function.
S_i = (A*S_i-1 + B) mod 2³² when i > 1.
Note: In this problem, the time limit is very tight. Using built-in data structures, such as set/unordered_set in C++ or TreeSet/HashSet in Java, may lead to a Time Limit Exceed verdict.

Output

Output a single line containing a single integer — sum of elements in the set after Q queries.

Constraints

Example

Input:
5 1 1 1

Output:
3


Input:
10000000 777777777 777777777 777777777

Output:
5362358669068782

Explanation:

The sequence {S_i} is 1, 2, 3, 4, 5:
Operation 1, 1 mod 2 = 1, add number [1 / 2] = 0 to set, sum is 0.
Operation 2, 2 mod 2 = 0, erase number [2 / 2] = 1 from set, 1 is not in set, so nothing happens, sum is 0.
Operation 3, 3 mod 2 = 1, add number [3 / 2] = 1 to set, sum is 1.
Operation 4, 4 mod 2 = 0, erase number [4 / 2] = 2 from set, 2 is not in set, so nothing happens, sum is 1.
Operation 5, 5 mod 2 = 1, add number [5 / 2] = 2 to set, sum is 3.
==================================EDITORIAL====================================

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Hash-Table

PROBLEM:

Given two types of queries:
1. Add the number to the set of numbers being maintained. 2. Remove the given number from the set if it exists in it.
The numbers to be inserted/deleted are generated according to the following scheme:
S$S$ = (a*Si−1$S_{i-1}$ + b) mod 232$2^{32}$,
where a$a$ and b$b$ are integers.
The sum of the numbers finally remaining in the set after all the operations is to be reported.

EXPLANATION:

Given the number of operations to be executed, i.e., q=107$q={10}^7$, it should be clear that the insertions and deletions from the set are to be done in O(1)$\mathcal{O}(1)$. Use of STL or pre-written libraries in C++/Java can't be used since they will definitely time out because of associated overheads.
Hash Table Solution One way is to write our own hash table. Editorialist's solution provides a standard implementation of Hash-Table with chaining to handle collision. For chaining, linked list has been used in the given solution. You can read more about it over the internet.
Bitset Solution A neater and more concise solution is using Bitset. Let's think about the naive solution to this problem first. If we could simply keep an array of length 232−1$2^{32}-1$, then direct insert/lookup in the array would have been possible. The the memory constraints don't allow that big an array. However, let us look at the constraints on the number being inserted/deleted into the set. We know they lie between 0 and 232−1$2^{32}-1$, i.e., they can be represented by 31 bits. Now, we can use a smart way to index numbers. Let us keep an array of length 226$2^{26}$. This is perfectly fine with the memory limits. Now, for a 31 bit integer x$x$, let the first 26 bits indicate the index in the array where x$x$ will reside. The rest 5 bits can be encoded in a 32 bit integer since only different 25$2^5$ possibilities exist. Please read setter's/tester's solutions for this approach.
There is one more intricacy here: calculating Si$S_i$. If we use the normal mod$mod$ operation present in some of the programming languages, the solution will exceed time limit. This is because mod$mod$ is a complex operation and performing it 107${10}^7$ times will not work. The observation is that we have to take mod$mod$ 232$2^{32}$. If we keep the data type of S$S$, a$a$, b$b$ to be unsigned, in that case, we will not have to use mod$mod$ operation because the range of unsigned int is 0$0$ to 232−1$2^{32}-1$. Thus, if S$S$ goes over 232$2^{32}$ it will automatically overflow around to greater than 0$0$. In other words, the compiler will perform the mod$mod$ function implicitly because of the overflow.

COMPLEXITY:

O(1)$\mathcal{O}(1)$ per insert and delete operation.
=========================================code===============================
1. #include <cstdio>
2. #include <iostream>
3. #include <cmath>
4. #include <string>
5. #include <list>
6. #include <vector>
7. #include <algorithm>
8. #include <functional>
9. #include <utility>
10. #include <set>
11. #include <map>
12. #include <complex>
13. #include <queue>
14. #include <stack>
15. #include <cstdlib>
16. #include <ctime>
17. #include <cstring>
18. #include <string.h>
20. using namespace std;
22. typedef unsigned int uint;
23. typedef long long int64;
24. typedef unsigned long long uint64;
25. typedef unsigned short ushort;
26. typedef unsigned char uchar;
27. typedef pair<int,int> ipair;
28. typedef vector<int> VI;
29. typedef vector<string> VS;
30. typedef vector<double> VD;
31. #define SIZE(A) ((int)(A.size()))
32. #define LENGTH(A) ((int)(A.length()))
33. #define MP(A,B) make_pair(A,B)
34. const double pi=acos(-1.0);
35. const double eps=1e-11;
36. #define FOR(i,a,b) for(int i=(a);i<(b);++i)
37. #define REP(i,a) for(int i=0;i<(a);++i)
38. #define ALL(a) (a).begin(),(a).end()
40.  
41. int64 s;
42. uint w[1<<26];
44. void add(uint n)
45. {
46. uint b=(((uint)1)<<(n&31));// finding which bit is it out or 32 bits
47. uint m=(n>>5);// index calculation which is least 26 bits
48. if (!(w[m]&b)) { s+=n; w[m]|=b; }
49. }
50. void remove(uint n)
51. {
52. uint b=(((uint)1)<<(n&31));// finding which bit is it out or 32 bits
53. uint m=(n>>5);// index calculation which is least 26 bits
54. if (w[m]&b) { s-=n; w[m]^=b; }
55. }
56. int main()
57. {
58.  
59. std::ios_base::sync_with_stdio(false);
60. int q;
61. uint s1,a,b;
62. cin>>q>>s1>>a>>b;
63. memset(w,0,sizeof(w));
64. s=0;
65. REP(step,q)
66. {
67. if (step>0) s1=a*s1+b;
68. if (s1&1)
69. {
70. uint v=s1>>1;
71. // cout<<"add"<<s1<<" "<<v<<endl;
72. add(s1/2);
75. }
77. else
78. {
79. uint v=s1>>1;
80. // cout<<"remove "<<s1<<" "<< v<<endl;
81. remove(s1/2);
82. }
84. }
85. cout<<s<<endl;
86. return 0;
87. }