Tanish69420

Untitled

Nov 9th, 2024
37
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 16.86 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <unordered_set>
  3. using namespace std;
  4. #pragma GCC optimize("Ofast")
  5. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
  6. #pragma GCC optimize("unroll-loops")
  7. #define ll long long
  8. #define vll vector<long long>
  9. #define vvll vector<vector<long long>>
  10. #define db double
  11. #define vi vector<int>
  12. #define vvi vector<vector<int>>
  13. #define pb push_back
  14. #define mp make_pair
  15. #define sorta(a) sort(a.begin(), a.end())
  16. #define sortd(a) sort(a.begin(), a.end(), greater<int>())
  17. #define vpll vector<pair<ll, ll>>
  18. #define forn(i, e) for (ll i = 0; i < e; i++)
  19. #define forsn(i, s, e) for (ll i = s; i < e; i++)
  20. #define rforn(i, s) for (ll i = s; i >= 0; i--)
  21. #define rforsn(i, s, e) for (ll i = s; i >= e; i--)
  22. #define pq priority_queue<ll>
  23. struct custom_hash
  24. {
  25. static uint64_t splitmix64(uint64_t x)
  26. {
  27. // http://xorshift.di.unimi.it/splitmix64.c
  28. x += 0x9e3779b97f4a7c15;
  29. x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  30. x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  31. return x ^ (x >> 31);
  32. }
  33.  
  34. size_t operator()(uint64_t x) const
  35. {
  36. static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  37. return splitmix64(x + FIXED_RANDOM);
  38. }
  39. };
  40. #define umap unordered_map<ll, ll, custom_hash>
  41. #define uset unordered_set<ll, custom_hash>
  42.  
  43. /*
  44.  
  45. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⣠⠤⠤⠒⠒⠂⠤⠤⣄⣀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  46. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⣠⠤⠤⠖⠒⠚⣉⣉⣩⣄⣤⡴⠶⠶⠛⠚⠓⠶⠦⢤⣤⣄⣌⣉⡙⠓⠒⠢⠤⠤⣄⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  47. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⡤⠤⠤⠖⠒⠚⣉⣉⣍⣤⢤⠴⠶⠖⠛⠚⠋⠉⠉⠀⠀⠀⢀⣀⣀⣠⣤⣤⣀⣀⡀⠀⠀⠈⠉⠉⠙⠛⠒⠳⠶⠤⣤⣤⣩⣉⡙⠓⠒⠒⠤⠤⣤⣀⣀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  48. ⠀⣀⡤⠤⠔⠒⠒⢊⣉⣉⣥⢤⠤⠶⠖⠞⠙⠋⠛⠉⠉⠀⠀⠀⣀⣀⣀⣤⣤⣤⣶⢶⡾⣟⣿⣻⣽⣻⢯⣟⣷⣻⣽⣻⣟⡿⣶⡶⣶⣤⣤⣤⣀⣀⣀⠀⠀⠀⠉⠉⠙⠛⠙⠲⠶⠦⢤⡤⣌⣉⣉⠓⠒⠂⠦⠤⡤⣄
  49. ⢠⡧⠴⠖⠚⠛⠉⠉⠉⠀⠀⠀⣀⣀⣀⣠⣤⣴⡴⣶⢶⣾⢿⣿⣻⣽⣻⡽⣯⣟⡾⣯⢿⡽⣞⡷⣯⣟⡿⣞⣷⣻⣞⡷⣯⣟⣷⣻⢷⣯⣟⣾⣻⡽⣯⢿⣟⣷⡶⣶⢦⣤⣤⣀⣀⣀⡀⠀⠀⠈⠉⠉⠙⠛⠒⠲⠶⢼
  50. ⢸⣆⣀⣠⣤⣦⢶⡶⣶⢾⣻⢿⣯⢿⡽⣯⣟⡾⣽⢯⡿⣞⣿⣞⣷⣯⣷⣿⣷⣯⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣾⣷⣿⣿⣷⣿⣾⣿⣿⣾⣽⣾⣷⣿⣽⣻⣞⣷⣻⡽⣯⣟⣷⣻⢿⣽⣻⢿⣻⢷⡶⣶⢦⣤⣤⣄⣀⣸
  51. ⢸⣿⣽⣳⣟⡾⣯⢿⡽⣯⣟⡿⣞⣯⣿⣷⣿⣿⣿⣿⠿⠿⠿⠛⠛⠛⠋⠉⠉⠉⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠉⠉⠉⠙⠛⠛⠛⠿⠿⠿⣿⣷⣿⣾⣽⣟⣾⡽⣯⣟⣯⢿⡽⣯⣟⡾⣽⣞⣿
  52. ⢸⣿⣳⣟⣾⡽⣯⣿⣽⣷⣿⣿⠿⠟⠛⠋⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡄⠀⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠙⠛⠻⠿⢿⣾⣯⣿⣽⣳⣯⣟⡷⣯⣿
  53. ⠸⣿⣳⣿⣾⣿⠿⠟⠛⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣤⣤⣿⣎⣿⣧⣀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠙⠻⠿⣷⣿⣽⣷⣻
  54. ⠀⢻⣿⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⣉⣽⣿⣿⣿⣿⣿⡿⣿⣦⣤⣴⠤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠙⢿⡟
  55. ⠀⢸⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡶⣟⣿⡏⠙⣾⣿⣿⣿⡿⣿⣿⣿⣦⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣻⡇
  56. ⠀⣸⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⡋⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣿⣿⣿⣿⡛⠿⢶⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣽⡇
  57. ⠀⢸⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠻⣿⠿⠿⠿⣿⣿⣥⣿⡩⢿⣿⣿⣿⣿⣿⣿⣿⠟⠾⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢾⡇
  58. ⠀⢸⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⡿⣿⣿⣟⠻⠿⠤⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢿⡇
  59. ⠀⢸⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⠟⣿⣿⣿⣿⣯⣿⣿⣿⣷⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣻⡇
  60. ⠀⢹⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⠋⣰⣿⣿⣿⣿⣷⣿⡿⢿⣿⡿⠦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣽⡇
  61. ⠀⢸⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⢋⣴⣿⣿⣿⣿⣟⣲⣿⣿⣦⣌⠛⠲⠦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢾⡇
  62. ⠀⢸⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⠶⣦⣄⠀⠀⠀⠀⠀⠀⢀⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⣿⣿⣿⣿⡙⠷⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣻⡇
  63. ⠀⢹⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⢿⣿⣿⣿⣷⣦⣀⠀⣠⣴⣿⣿⣭⣭⣬⣻⣿⣿⣿⣿⣿⣾⣿⣿⡿⠿⣟⠒⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡶⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣽⡇
  64. ⠀⢸⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣇⣿⠋⢿⣛⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⡟⢿⣿⣿⣿⣿⣿⣿⣷⣦⡀⢀⡄⠀⠀⠀⠀⠀⠀⠀⣰⡟⠁⣀⡾⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢾⡇
  65. ⠀⢸⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⣿⣯⣀⣀⠙⢿⣿⠃⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⠻⠿⣿⡷⣌⠉⠉⠀⠀⠀⠀⠀⠀⠀⢠⣿⣇⣴⡟⠁⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢿⡇
  66. ⠀⢸⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣏⣯⣿⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡍⢿⡀⠀⠀⠙⠒⠂⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⡿⠀⣤⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⡇
  67. ⠀⢸⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣧⣿⣿⠙⠿⣟⡻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡘⢿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢿⣿⣧⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠃
  68. ⠀⠠⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⡇⢿⡄⠀⠀⠉⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣌⣿⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁
  69. ⠀⠀⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠟⠁⢻⣼⣧⠀⠀⠀⠀⠀⠉⠉⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⢿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡿⠀
  70. ⠀⠀⢸⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣿⣆⠀⠀⠀⠀⠀⠀⠈⠻⣧⡈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⣿⠊⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⡇⠀
  71. ⠀⠀⠘⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣿⣿⣷⡄⠀⠀⠀⠀⠀⠀⠈⠻⣦⣝⢿⣿⣿⣿⣿⣿⣇⣼⣿⣿⣿⣿⣿⣿⣷⡄⠀⠀⠀⠀⠀⢰⡿⢀⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⠂⠀
  72. ⠀⠀⠀⢻⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢯⣽⠇⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⢷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠀⠀⢀⣴⣟⣠⣿⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⡏⠀⠀
  73. ⠀⠀⠀⠸⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⣿⣿⣾⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⠃⠀⠀
  74. ⠀⠀⠀⠀⢻⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣯⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢻⣿⢿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⡏⠀⠀⠀
  75. ⠀⠀⠀⠀⠈⣿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢿⣿⣿⣾⡿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⢸⠿⣿⡿⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠀⠀⠀
  76. ⠀⠀⠀⠀⠀⠸⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⣿⣿⣧⡏⣼⣿⣿⣿⣿⣿⣿⣿⠟⠀⢼⣠⣿⠁⠓⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⠇⠀⠀⠀⠀
  77. ⠀⠀⠀⠀⠀⠀⢻⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣄⣀⡀⠀⡀⠀⠀⠀⠀⠈⢿⣿⣟⣿⣿⣿⣿⣿⣿⣿⠟⠃⠀⠀⢸⡟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⡏⠀⠀⠀⠀⠀
  78. ⠀⠀⠀⠀⠀⠀⠀⢿⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢿⣿⣿⣿⣿⣿⣷⣒⠦⢤⣄⣠⡿⣧⢿⡛⣿⣿⣿⠏⠁⠀⠀⠀⠀⠺⠅⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⡟⠀⠀⠀⠀⠀⠀
  79. ⠀⠀⠀⠀⠀⠀⠀⠈⢿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠁⠁⠈⠉⠉⠙⠛⠓⠿⣿⣿⣿⣾⣷⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⡿⠁⠀⠀⠀⠀⠀⠀
  80. ⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠙⠁⠈⢻⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⡿⠁⠀⠀⠀⠀⠀⠀⠀
  81. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⡯⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀
  82. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡴⣫⡾⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
  83. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  84. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢻⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣶⡟⢳⢲⣶⣶⡄⠀⠀⠀⠀⢠⣾⣿⣿⡟⠁⠀⠀⠀⠀⢠⣶⣶⣶⣶⣶⣤⣤⣤⣴⣶⡖⠉⠀⠀⠀⠀⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  85. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢻⣧⡀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣇⡀⠀⠀⠙⢧⡀⠀⠀⠀⣿⣥⣿⠟⠀⠀⠀⠀⠀⢰⣿⣿⠄⠀⢀⣼⠟⠉⠁⠁⠀⠀⠀⠀⠀⢀⣼⡟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  86. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣷⡄⠀⠀⠀⠀⠀⠀⠀⠀⠉⠛⠿⣿⣶⣤⡀⠀⠀⠀⠀⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠉⠁⢀⣀⣾⣏⣠⠀⠀⠀⠀⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  87. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢿⣦⠀⠀⠀⠀⠀⠀⢠⣶⣦⠀⠀⠉⠛⣿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣦⠀⠀⠀⠉⣽⡟⠉⠁⠀⠀⠀⠀⠀⠀⣴⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  88. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠻⣷⣄⠀⠀⠀⠀⢹⣆⠀⠀⠀⠀⠀⣼⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⡀⠀⠀⠀⢀⣼⡟⠀⠀⠀⠀⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  89. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⣦⡀⠀⠀⠀⠉⠳⠶⠴⠶⠞⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⠶⠦⠶⠟⠋⠀⠀⠀⠀⠀⠀⢀⣼⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  90. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  91. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  92. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  93. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢻⣶⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣶⠟⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  94. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⢷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡾⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  95. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠻⣷⣤⡀⠀⠀⠀⠀⠀⢀⣤⣾⠟⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  96. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠻⣷⣦⣀⣴⡾⠟⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  97. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⣛⡉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
  98.  
  99. */
  100. ll pow(ll base, ll exponent, ll modulus)
  101. {
  102. ll result = 1;
  103. base = base % modulus;
  104. while (exponent > 0)
  105. {
  106. if (exponent % 2 == 1)
  107. {
  108. result = (result * base) % modulus;
  109. }
  110. exponent = exponent >> 1;
  111. base = (base * base) % modulus;
  112. }
  113. return result;
  114. }
  115.  
  116. // Print function without newline
  117. template <typename T>
  118. void prints_helper(const T &t)
  119. {
  120. cout << t;
  121. }
  122.  
  123. template <typename T, typename... Args>
  124. void prints_helper(const T &t, const Args &...args)
  125. {
  126. cout << t;
  127. prints_helper(args...);
  128. }
  129.  
  130. template <typename... Args>
  131. void prints(const Args &...args)
  132. {
  133. prints_helper(args...);
  134. }
  135.  
  136. // Print function with newline
  137.  
  138. template <typename T>
  139. void print_helper(const T &t)
  140. {
  141. cout << t << " ";
  142. }
  143.  
  144. template <typename T>
  145. void print_helper(const vector<T> &v)
  146. {
  147. cout << "[";
  148. for (auto it = v.begin(); it != v.end(); ++it)
  149. {
  150. if (it != v.begin())
  151. cout << ", ";
  152. cout << *it;
  153. }
  154. cout << "]";
  155. }
  156.  
  157. template <typename T>
  158. void print_helper(const set<T> &s)
  159. {
  160. cout << "{";
  161. for (auto it = s.begin(); it != s.end(); ++it)
  162. {
  163. if (it != s.begin())
  164. cout << ", ";
  165. cout << *it;
  166. }
  167. cout << "}";
  168. }
  169.  
  170. template <typename T>
  171. void print_helper(const unordered_set<T, custom_hash> &us)
  172. {
  173. cout << "{";
  174. for (auto it = us.begin(); it != us.end(); ++it)
  175. {
  176. if (it != us.begin())
  177. cout << ", ";
  178. cout << *it;
  179. }
  180. cout << "}";
  181. }
  182.  
  183. template <typename K, typename V>
  184. void print_helper(const map<K, V> &m)
  185. {
  186. cout << "{";
  187. for (auto it = m.begin(); it != m.end(); ++it)
  188. {
  189. if (it != m.begin())
  190. cout << ", ";
  191. cout << it->first << ": " << it->second;
  192. }
  193. cout << "}";
  194. }
  195.  
  196. template <typename K, typename V>
  197. void print_helper(const unordered_map<K, V, custom_hash> &um)
  198. {
  199. cout << "{";
  200. for (auto it = um.begin(); it != um.end(); ++it)
  201. {
  202. if (it != um.begin())
  203. cout << ", ";
  204. cout << it->first << ": " << it->second;
  205. }
  206. cout << "}";
  207. }
  208.  
  209. template <typename T, typename... Args>
  210. void print_helper(const T &t, const Args &...args)
  211. {
  212. print_helper(t);
  213. print_helper(args...);
  214. }
  215.  
  216. template <typename... Args>
  217. void print(const Args &...args)
  218. {
  219. print_helper(args...);
  220. cout << endl;
  221. }
  222.  
  223. int main()
  224. {
  225. ios_base::sync_with_stdio(false);
  226. cin.tie(NULL);
  227. cout.tie(NULL);
  228. int t;
  229. cin >> t;
  230. while (t--)
  231. {
  232. ll n, k;
  233. cin >> n >> k;
  234. vector<ll> a(n);
  235. vector<ll> b;
  236.  
  237. forn(i, n)
  238. {
  239. cin >> a[i];
  240. }
  241. sorta(a);
  242. ll sum = 0;
  243. forn(i, n)
  244. {
  245. if (a[i] > k)
  246. {
  247. b.pb(a[i]);
  248. }
  249. else
  250. {
  251. sum += a[i];
  252. }
  253. }
  254.  
  255. ll i = 0;
  256. while (i < (static_cast<ll>(b.size()) - 1))
  257. {
  258. ll temp = 0;
  259. temp += b[i] - k;
  260. b[i + 1] -= temp;
  261. sum += k;
  262. i++;
  263. }
  264.  
  265. sum += b[static_cast<ll>(b.size()) - 1];
  266. print(sum);
  267. }
  268. return 0;
  269. }
Advertisement
Add Comment
Please, Sign In to add comment