/// kazuki08
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define ar array
//#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

__int128 ans;

__int128  gcd(__int128  a, __int128  b, __int128 & x, __int128 & y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    __int128  x1, y1;
    __int128  d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

bool find_any_solution(__int128  a, __int128  b, __int128  c, __int128  &x0, __int128  &y0, __int128  &g) {
    g = gcd(abs(a), abs(b), x0, y0);
    if (c % g) {
        return false;
    }

    x0 *= c / g;
    y0 *= c / g;
    if (a < 0) x0 = -x0;
    if (b < 0) y0 = -y0;
    return true;
}

void shift_solution(__int128  & x, __int128  & y, __int128  a, __int128  b, __int128  cnt) {
    x += cnt * b;
    y -= cnt * a;
}

__int128  find_all_solutions(__int128  a, __int128  b, __int128  c, __int128  minx, __int128  maxx, __int128  miny, __int128  maxy) {
    __int128  x, y, g;
    if (!find_any_solution(a, b, c, x, y, g))
        return 0;
    a /= g;
    b /= g;

    __int128  sign_a = a > 0 ? +1 : -1;
    __int128  sign_b = b > 0 ? +1 : -1;

    shift_solution(x, y, a, b, (minx - x) / b);
    if (x < minx)
        shift_solution(x, y, a, b, sign_b);
    if (x > maxx)
        return 0;
    __int128  lx1 = x;

    shift_solution(x, y, a, b, (maxx - x) / b);
    if (x > maxx)
        shift_solution(x, y, a, b, -sign_b);
    __int128  rx1 = x;

    shift_solution(x, y, a, b, -(miny - y) / a);
    if (y < miny)
        shift_solution(x, y, a, b, -sign_a);
    if (y > maxy)
        return 0;
    __int128  lx2 = x;

    shift_solution(x, y, a, b, -(maxy - y) / a);
    if (y > maxy)
        shift_solution(x, y, a, b, sign_a);
    __int128  rx2 = x;

    if (lx2 > rx2)
        swap(lx2, rx2);
    __int128  lx = max(lx1, lx2);
    __int128  rx = min(rx1, rx2);

    if (lx > rx)
        return 0;
    ans = min(ans,a*lx);
    return (rx - lx) / abs(b) + 1;
}

__int128 n;
void print(__int128 x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

__int128 read() {
    __int128 x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
  
  n = read();
  if(n==1){
    cout << 1 << endl;return 0;
  }
  if(n%2){
    ans = n-1;
  }
  else {
    ans = 2*n;
  }
  int x = 2*n;
  for(int i=1;i*i<=2*n;i++){
    if(x%i==0){
      __int128 a1 = i;
      __int128  a2 = x/i;
      if(a1<a2)swap(a1,a2);
      __int128  gc = __gcd(a1,a2);
      if(gc>1)continue;
      // print(gc);cout<<endl;
      // print(a1);
      // print(a2);
      find_all_solutions(a1,-a2,-1,1,1e17,1,1e17);
      // printf("\n");
      find_all_solutions(a2,-a1,-1,1,1e17,1,1e17);
      // printf("\n");
    }
  }
  print(ans);

return 0;
}
///....


Measured memory_bytes: 3660