Given a permutation P={1,2,...,n} and q queries of the form (x,y), swap elements with indices x and y. Find the number of inversions in P after each query.
### Input
- The first line contains two integers n,q.
- The next q lines, each line contains two integers x,y, a query.
### Output
- Print the answer for each query.
### Constraints
- 1≤n,q≤105.
- 1≤x,y≤n.
### Example
Input:
5445242522
Output:
1433
