stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;

const int N = 300003;

const long long infll = 1000000000000000000;

int arr[N];

long long lef[N], righ[N];

int main()

{

    int n;

    scanf("%d",&n);

    for(int i = 0;i<3*n;i++)

        scanf("%d",&arr[i]);

    for(int i = 0;i<N;i++)

        lef[i] = -infll, righ[i] = infll;

    long long sum = 0;

    multiset<int> s;

    for(int i = 0;i<3*n;i++) {

        s.insert(arr[i]);

        sum += arr[i];

        if(s.size() == n) {

            lef[i] = sum;

        } else if(s.size() > n) {

            sum -= *s.begin();

            s.erase(s.begin());

            lef[i] = sum;

        }

    }

    s.clear();

    sum = 0;

    for(int i = 3*n-1;i>=0;i--) {

        sum += arr[i];

        s.insert(arr[i]*-1);

        if(s.size() == n) {

            righ[i] = sum;

        } else if (s.size() > n) {

            sum -= *(s.begin()) * -1;

            s.erase(s.begin());

            righ[i] = sum;

        }

    }

    for(int i = 1;i<N;i++)

        lef[i] = max(lef[i],lef[i-1]);

    for(int i = N-2;i>=0;i--)

        righ[i] = min(righ[i], righ[i+1]);

    long long ans = -infll;

    for(int i = 0;i<3*n;i++)

        ans = max(ans,lef[i] - righ[i+1]);

    printf("%lld",ans);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 10.7334887182381x):
#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <numeric>

#include <vector>

#include <string>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <climits>

#include <cmath>

#include <cstring>

#include <unordered_set>

#include <unordered_map>

using namespace std;



#define pb push_back

#define fst first

#define snd second



typedef long long ll;

typedef pair<int,int> pii;

template<typename T> using min_queue=priority_queue<T,vector<T>,greater<T>>;



const ll MOD=1e9+7;



int N;

ll a[300100];

ll mx[300100];

ll mn[300100];



int main(){

  ios::sync_with_stdio(0);cin.tie(0);



  cin>>N;

  for(int i=0;i<3*N;i++) cin>>a[i];



  {

    min_queue<ll> q;

    ll s=0;

    for (int i=0;i<2*N;i++) {

      q.push(a[i]), s+=a[i];

      if (q.size() > N) s-=q.top(),q.pop();

      if (i >= N-1) mx[i] = s;

    }

  }



  {

    priority_queue<ll> q;

    ll s=0;

    for (int i=3*N-1;i>=N;i--) {

      q.push(a[i]), s+=a[i];

      if (q.size() > N) s-=q.top(),q.pop();

      if (i <= 2*N) mn[i] = s;

    }

  }



  ll res=-1e18;



  for (int i=N-1;i<2*N;i++) res=max(res, mx[i]-mn[i+1]);



  cout<<res<<endl;



  return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



int main() {

	int a, b;

	scanf("%d%d", &a, &b);

	if (b == 1) {

		cout << 0 << endl;

		return 0;

	}

	else cout << a - b << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.198454460755294x):
#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int main()

{

	int n,m,a[10010];

	while(~scanf("%d%d",&n,&m))

	{

		for(int i=0;i<m;i++)

		a[i]=1;

		int sum=n-m;

		a[m-1]+=sum;

		printf("%d\n",a[m-1]-a[0]);

	}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main()

{int a,b,c;

 cin>>a>>b>>c;

 cout<<(a-c)/(b+c)<<endl;

} 

// Faster C++ solution for the same problem (measured speedup: 5.254661328971495x):
#include<stdio.h>

int main()

{

	int x, y, z;

	scanf("%d %d %d",&x,&y,&z);

	x = x - z;

	printf("%d\n",x/(y+z));

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int a,b,c;

int main(){

    cin>>a>>b>>c;

    cout<<(a-c)/(b+c)<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.2549749319512635x):
#include<stdio.h>

int main()

{

	int x, y, z;

	scanf("%d %d %d",&x,&y,&z);

	x = x - z;

	printf("%d\n",x/(y+z));

}
// Slower C++ solution:
#include<iostream>

using namespace std;

int main()

{

    int a,b,c;

    cin>>a>>b>>c;

    cout<<(a-c)/(b+c)<<endl;

}

// Faster C++ solution for the same problem (measured speedup: 5.159128128492373x):
#include<stdio.h>

int x,y,z,s,ans;

template<typename TYPE>

inline void read(TYPE&x){

	x=0;int w=1;register char c=getchar();for(;c<'0'||c>'9';c=getchar()) if (c=='-') w=-1;

	for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=getchar());x*=w;

}

int main(){

	read(x);read(y);read(z);

	for(;s+z<=x;s=s+z+y) ans++;

	return printf("%d\n",--ans),0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

using namespace std;

int main()

{

	int x,y,z,ans;

	scanf("%d%d%d",&x,&y,&z);

	ans=(x-z)/(y+z);

	printf("%d",ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.092901560555719x):
#include<stdio.h>

int x,y,z,s,ans;

template<typename TYPE>

inline void read(TYPE&x){

	x=0;int w=1;register char c=getchar();for(;c<'0'||c>'9';c=getchar()) if (c=='-') w=-1;

	for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=getchar());x*=w;

}

int main(){

	read(x);read(y);read(z);

	for(;s+z<=x;s=s+z+y) ans++;

	return printf("%d\n",--ans),0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main(){

	int a,b,c;

	cin >> a >> b >> c;

	cout << (a-c)/(b+c) << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.159128128492373x):
#include<stdio.h>

int x,y,z,s,ans;

template<typename TYPE>

inline void read(TYPE&x){

	x=0;int w=1;register char c=getchar();for(;c<'0'||c>'9';c=getchar()) if (c=='-') w=-1;

	for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=getchar());x*=w;

}

int main(){

	read(x);read(y);read(z);

	for(;s+z<=x;s=s+z+y) ans++;

	return printf("%d\n",--ans),0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

int main()

{

	int a,b,c;

	cin>>a>>b>>c;

	cout<<(a-c)/(b+c)<<endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.159128128492373x):
#include<stdio.h>

int x,y,z,s,ans;

template<typename TYPE>

inline void read(TYPE&x){

	x=0;int w=1;register char c=getchar();for(;c<'0'||c>'9';c=getchar()) if (c=='-') w=-1;

	for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=getchar());x*=w;

}

int main(){

	read(x);read(y);read(z);

	for(;s+z<=x;s=s+z+y) ans++;

	return printf("%d\n",--ans),0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main()

{

    int x,y,z;

    cin>>x>>y>>z;

    cout<<(x-z)/(z+y)<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.159128128492373x):
#include<stdio.h>

int x,y,z,s,ans;

template<typename TYPE>

inline void read(TYPE&x){

	x=0;int w=1;register char c=getchar();for(;c<'0'||c>'9';c=getchar()) if (c=='-') w=-1;

	for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=getchar());x*=w;

}

int main(){

	read(x);read(y);read(z);

	for(;s+z<=x;s=s+z+y) ans++;

	return printf("%d\n",--ans),0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

long long x,y,z,sum=0;

int main() {

    scanf("%lld%lld%lld",&x,&y,&z);

    cout<<(x-z)/(z+y)<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.207672389956651x):
#include<algorithm>

#include<stdio.h>

#include<cmath>

using namespace std;

int main(){

	int x,y,z;

	scanf("%d%d%d",&x,&y,&z);

	int ans=floor((x-z)/(y+z));

	printf("%d\n",ans); 

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main()

{

	int x,y,z;

	cin>>x>>y>>z;

	int s=0;x-=z;

	while((x-y-z)>=0)

	{

		s++;

		x=x-y-z;

	}

	cout<<s<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.284462943531458x):
#include<algorithm>

#include<stdio.h>

#include<cmath>

using namespace std;

int main(){

	int x,y,z;

	scanf("%d%d%d",&x,&y,&z);

	int ans=floor((x-z)/(y+z));

	printf("%d\n",ans); 

	return 0;

}
// Slower C++ solution:
#include<iostream>

using namespace std;

int main(){

    int x,y,z;

    cin>>x>>y>>z;

    cout<<(x-z)/(y+z)<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.254070741616721x):
#include<algorithm>

#include<stdio.h>

#include<cmath>

using namespace std;

int main(){

	int x,y,z;

	scanf("%d%d%d",&x,&y,&z);

	int ans=floor((x-z)/(y+z));

	printf("%d\n",ans); 

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <vector>

using namespace std;



long long cnt;

int l;

int A[1000000];

int n;

vector<int> G;



// ??????g????????????????????\?????????

void insertionSort(int A[], int n, int g) {

  for ( int i = g; i < n; i++ ) {

    int v = A[i];

    int j = i - g;



    while ( j >= 0 && A[j] > v ) {

      A[j + g] = A[j];

      j -= g;

      cnt++;

    }

    A[j + g] = v;

  }

}



void shellSort(int A[], int n) {

  for ( int h = 1; ;) {

    if ( h > n ) break;

    G.push_back(h);

    h = 3*h + 1;

  }



  for ( int i = G.size()-1; i >= 0; i-- ) {

    insertionSort(A, n, G[i]);

  }

}



int main() {

  cin >> n;



  for ( int i = 0; i < n; i++ ) scanf("%d", &A[i]);

  cnt = 0;



  shellSort(A, n);



  cout << G.size() << endl;

  for ( int i = G.size() - 1; i >= 0; i-- ) {

    printf("%d", G[i]);

    if ( i ) printf(" ");

  }

  printf("\n");

  printf("%d\n", cnt);

  for ( int i = 0; i < n; i++ ) printf("%d\n", A[i]);



  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.5514519536653513x):
#include<stdio.h>



int insertionSort(int A[], int n, int g) {

  int cnt = 0;

  for (int i = g; i < n; i++) {

    int v = A[i];

    int j = i - g;

    while ( j >= 0 && v < A[j]) {

      A[j + g] = A[j];

      j -= g;

      cnt++;

    }

    A[j + g] = v;

  }



  return cnt;

}



void shellSort(int A[], int n) {

  int im, m = 1, v = 1, G[100], sum = 0;

  for ( im = 0; v <= n; im++ ) {

    G[im] = v;

    m *= 3;

    v += m;

  }



  printf("%d\n", im);

  for ( int i = im - 1; i >= 0; i-- ) {

    if ( i != (im - 1) ) printf(" ");

    printf("%d", G[i]);

    sum += insertionSort(A, n, G[i]);

  }



  printf("\n%d\n", sum);

  for ( int i = 0; i < n; i++ ) {

    printf("%d\n", A[i]);

  }

}



int main() {

  int n, A[1000000];

  scanf("%d", &n);



  for ( int i = 0; i < n; i++ ) scanf("%d", &A[i]);



  shellSort(A, n);



  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>



using namespace std;



int main(void) {



    int n;

    cin >> n;



    int *arr = new int[n];

    for (int i = 0; i < n; ++i) {

        cin >> arr[i];

    }



    int m = 1;

    for (int f = 4; m < 100; ++m, f<<=1) {

        if (n / f == 0)

            break;

    }



    int *G = new int[m];

    G[m-1] = 1;

    for (int i = m - 2, f = 4; i >= 0; --i, f<<=1) {

        G[i] = f;

    }



    int count = 0;

    for (int i = 0; i < m; ++i) {

        int g = G[i];

        for (int j = g; j < n; ++j) {

            int k, key = arr[j];

            for (k = j - g; k >= 0 && arr[k] > key; k-=g, ++count) {

                arr[k + g] = arr[k];

            }

            arr[k+g] = key;

        }

    }



    printf("%d\n", m);

    for (int i = 0; i < m - 1; ++i) {

        printf("%d ", G[i]);

    }

    printf("%d\n", G[m - 1]);

    printf("%d\n", count);

    for (int i = 0; i < n; ++i) {

        printf("%d\n", arr[i]);

    }



    delete[] arr;

    delete[] G;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.163428175398059x):
#include <cstdio>

#include <cstdlib>



using namespace std;



int main(void) {



    int n;

    scanf("%d", &n);



    int *arr = static_cast<int*>(malloc(sizeof(int)*n));

    for (int i = 0; i < n; ++i) {

        scanf("%d", &arr[i]);

    }



    int m = 1;

    for (int f = 4; m < 100; ++m, f<<=1) {

        if (n / f == 0)

            break;

    }



    int *G = static_cast<int*>(malloc(sizeof(int)*m));

    G[m-1] = 1;

    for (int i = m - 2, f = 4; i >= 0; --i, f<<=1) {

        G[i] = f;

    }



    int count = 0;

    for (int i = 0; i < m; ++i) {

        int g = G[i];

        for (int j = g; j < n; ++j) {

            int k, key = arr[j];

            for (k = j - g; k >= 0 && arr[k] > key; k-=g, ++count) {

                arr[k + g] = arr[k];

            }

            arr[k+g] = key;

        }

    }



    printf("%d\n", m);

    for (int i = 0; i < m - 1; ++i) {

        printf("%d ", G[i]);

    }

    printf("%d\n", G[m - 1]);

    printf("%d\n", count);

    for (int i = 0; i < n; ++i) {

        printf("%d\n", arr[i]);

    }



    free(arr);

    free(G);



    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <utility>

#include <algorithm>

#include <cmath>

using namespace std;



typedef vector<int> vi;



template<typename T>

static inline void p(T x) { cout << x << endl; }



int main()

{

    cin.sync_with_stdio(false);



	int n, cnt = 0;

	cin >> n;



	vi A(n), G;

	for (int &x: A)

		cin >> x;



	for (int i = 1, x = 1; x <= n; x = (pow(3, ++i) - 1) / 2)

		G.push_back(x);

	reverse(G.begin(), G.end());



	for (int g: G)

		for (int i = g; i < n; i++) {

			int v = A[i], j = i - g;

			for(; j >= 0 && A[j] > v; j -= g)

				A[j+g] = A[j], cnt++;

			A[j+g] = v;

		}



	p(G.size());

	for (int &x: G)

		cout << (&x == &G[0] ? "" : " ") << x;

	p("");

	p(cnt);

	for (int x: A)

		p(x);

}


// Faster C++ solution for the same problem (measured speedup: 1.10280594079841x):
#include <cstdio>

#include <vector>

#include <utility>

#include <algorithm>

#include <cmath>

using namespace std;



typedef vector<int> vi;



static inline void p(int x) { printf("%d\n", x); }



int main()

{



	int n, cnt = 0;

	scanf("%d", &n);



	vi A(n), G;

	for (int &x: A)

		scanf("%d", &x);



	for (int i = 1, x = 1; x <= n; x = (pow(3, ++i) - 1) / 2)

		G.push_back(x);

	reverse(G.begin(), G.end());



	for (int g: G)

		for (int i = g; i < n; i++) {

			int v = A[i], j = i - g;

			for(; j >= 0 && A[j] > v; j -= g)

				A[j+g] = A[j], cnt++;

			A[j+g] = v;

		}



	p(G.size());

	for (int &x: G)

		printf("%s%d", (&x == &G[0] ? "" : " "), x);

	puts("");

	p(cnt);

	for (int x: A)

		p(x);

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <utility>

#include <algorithm>

#include <cmath>

using namespace std;



typedef vector<int> vi;



template<typename T>

static inline void p(T x) { cout << x << endl; }



int main()

{

	ios::sync_with_stdio(false);

	cin.tie(0);



	int n, cnt = 0;

	cin >> n;



	vi A(n), G;

	for (int &x: A)

		cin >> x;



	for (int i = 1, x = 1; x <= n; x = (pow(3, ++i) - 1) / 2)

		G.push_back(x);

	reverse(G.begin(), G.end());



	for (int g: G)

		for (int i = g; i < n; i++) {

			int v = A[i], j = i - g;

			for(; j >= 0 && A[j] > v; j -= g)

				A[j+g] = A[j], cnt++;

			A[j+g] = v;

		}



	p(G.size());

	for (int &x: G)

		cout << (&x == &G[0] ? "" : " ") << x;

	p("");

	p(cnt);

	for (int x: A)

		p(x);

}


// Faster C++ solution for the same problem (measured speedup: 1.1030070676093033x):
#include <cstdio>

#include <vector>

#include <utility>

#include <algorithm>

#include <cmath>

using namespace std;



typedef vector<int> vi;



static inline void p(int x) { printf("%d\n", x); }



int main()

{



	int n, cnt = 0;

	scanf("%d", &n);



	vi A(n), G;

	for (int &x: A)

		scanf("%d", &x);



	for (int i = 1, x = 1; x <= n; x = (pow(3, ++i) - 1) / 2)

		G.push_back(x);

	reverse(G.begin(), G.end());



	for (int g: G)

		for (int i = g; i < n; i++) {

			int v = A[i], j = i - g;

			for(; j >= 0 && A[j] > v; j -= g)

				A[j+g] = A[j], cnt++;

			A[j+g] = v;

		}



	p(G.size());

	for (int &x: G)

		printf("%s%d", (&x == &G[0] ? "" : " "), x);

	puts("");

	p(cnt);

	for (int x: A)

		p(x);

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <utility>

#include <algorithm>

#include <cmath>

using namespace std;



typedef vector<int> vi;



template<typename T>

static inline void p(T x) { cout << x << endl; }



int main()

{

    cin.sync_with_stdio(false);



	int n, cnt = 0;

	cin >> n;



	vi A(n), G;

	for (int &x: A)

		cin >> x;



	for (int i = 1, x = 1; x <= n; x = (pow(3, ++i) - 1) / 2)

		G.push_back(x);

	reverse(G.begin(), G.end());



	for (int g: G)

		for (int i = g; i < n; i++) {

			int v = A[i], j = i - g;

			for(; j >= 0 && A[j] > v; j -= g)

				A[j+g] = A[j], cnt++;

			A[j+g] = v;

		}



	p(G.size());

	for (int &x: G)

		cout << (&x == &G[0] ? "" : " ") << x;

	p("");

	p(cnt);

	for (int x: A)

		p(x);

}


// Faster C++ solution for the same problem (measured speedup: 1.1122499414390434x):
#include <cstdio>

#include <vector>

#include <utility>

#include <algorithm>

#include <cmath>

using namespace std;



static inline void p(int x) { printf("%d\n", x); }



int main()

{

	int n, cnt = 0;

	scanf("%d", &n);



	vector<int> A(n), G;

	for (int &x: A)

		scanf("%d", &x);



	for (int i = 1, x = 1; x <= n; x = (pow(3, ++i) - 1) / 2)

		G.push_back(x);

	reverse(G.begin(), G.end());



	for (int g: G)

		for (auto b = A.begin(), i = b + g, e = A.end(); i != e; i++) {

			int v = *i;

			auto j = i - g;

			for(; j >= b && *j > v; j -= g)

				*(j + g) = *j, cnt++;

			*(j + g) = v;

		}



	p(G.size());

	for (int &x: G)

		printf("%s%d", (&x == &G[0] ? "" : " "), x);

	puts("");

	p(cnt);

	for (int x: A)

		p(x);

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <utility>

#include <algorithm>

#include <cmath>

using namespace std;



typedef vector<int> vi;



template<typename T>

static inline void p(T x) { cout << x << endl; }



int main()

{

	ios::sync_with_stdio(false);

	cin.tie(0);



	int n, cnt = 0;

	cin >> n;



	vi A(n), G;

	for (int &x: A)

		cin >> x;



	for (int i = 1, x = 1; x <= n; x = (pow(3, ++i) - 1) / 2)

		G.push_back(x);

	reverse(G.begin(), G.end());



	for (int g: G)

		for (int i = g; i < n; i++) {

			int v = A[i], j = i - g;

			for(; j >= 0 && A[j] > v; j -= g)

				A[j+g] = A[j], cnt++;

			A[j+g] = v;

		}



	p(G.size());

	for (int &x: G)

		cout << (&x == &G[0] ? "" : " ") << x;

	p("");

	p(cnt);

	for (int x: A)

		p(x);

}


// Faster C++ solution for the same problem (measured speedup: 1.1124527906216257x):
#include <cstdio>

#include <vector>

#include <utility>

#include <algorithm>

#include <cmath>

using namespace std;



static inline void p(int x) { printf("%d\n", x); }



int main()

{

	int n, cnt = 0;

	scanf("%d", &n);



	vector<int> A(n), G;

	for (int &x: A)

		scanf("%d", &x);



	for (int i = 1, x = 1; x <= n; x = (pow(3, ++i) - 1) / 2)

		G.push_back(x);

	reverse(G.begin(), G.end());



	for (int g: G)

		for (auto b = A.begin(), i = b + g, e = A.end(); i != e; i++) {

			int v = *i;

			auto j = i - g;

			for(; j >= b && *j > v; j -= g)

				*(j + g) = *j, cnt++;

			*(j + g) = v;

		}



	p(G.size());

	for (int &x: G)

		printf("%s%d", (&x == &G[0] ? "" : " "), x);

	puts("");

	p(cnt);

	for (int x: A)

		p(x);

}
// Slower C++ solution:
#include<iostream>

using namespace std;



int cnt;



void insertionSort(int* a, int n, int g){



    int i, j, v;



    for(i = g; i < n; i++){

        v = a[i];

        j = i - g;

        while((j >= 0) && (a[j] > v)){

            a[j + g] = a[j];

            j = j - g;

            cnt++;

        };

        a[j + g] = v;

    }

}



void shellsort(int* a, int n)

{

    cnt = 0;

    int i, p;

    int m;

    int G[15];



    p = 1;

    for(i = 1; i < 20; i++){

        p = p * 3;

        if(p - 1 > 2 * n) break;

    }

    if(i > 1) i = i - 1;

    m = i;



    p = 1;

    for(i = 0; i < m; i++){

        p = p * 3;

        G[m - 1 - i] = (p - 1) / 2;

    }

    cout << m << endl;

    for(i = 0; i < m - 1; i++) cout << G[i] << " ";

    cout << G[m - 1] << endl;



    for(int i = 0; i < m; i++){

        insertionSort(a, n, G[i]);

    }

}



int main()

{

    int i, A[1000000], n;

    cin >> n;

    for(i = 0; i < n; i++) cin >> A[i];



    shellsort(A, n);

    cout << cnt << endl;

    for(i = 0; i < n; i++) cout << A[i] << endl;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.8447194958071313x):
#include<stdio.h>



int cnt;



void insertionSort(int* a, int n, int g){



    int i, j, v;



    for(i = g; i < n; i++){

        v = a[i];

        j = i - g;

        while((j >= 0) && (a[j] > v)){

            a[j + g] = a[j];

            j = j - g;

            cnt++;

        };

        a[j + g] = v;

    }

}



void shellsort(int* a, int n)

{

    cnt = 0;

    int i, p;

    int m;

    int G[15];



    p = 1;

    for(i = 1; i < 20; i++){

        p = p * 3;

        if(p - 1 > 2 * n) break;

    }

    if(i > 1) i = i - 1;

    m = i;



    p = 1;

    for(i = 0; i < m; i++){

        p = p * 3;

        G[m - 1 - i] = (p - 1) / 2;

    }

    printf("%d\n", m);

    for(i = 0; i < m - 1; i++) printf("%d ", G[i]);

    printf("%d\n", G[m - 1]);



    for(int i = 0; i < m; i++){

        insertionSort(a, n, G[i]);

    }

}



int main()

{

    int i, A[1000000], n;

    scanf("%d", &n);

    for(i = 0; i < n; i++) scanf("%d", &A[i]);



    shellsort(A, n);

    printf("%d\n", cnt);

    for(i = 0; i < n; i++) printf("%d\n", A[i]);



    return 0;

}
// Slower C++ solution:
#ifdef ConanYu

#include "local.hpp"

#else

#pragma GCC optimize("-O3")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void Main();

#define debug(...) do { } while(0)

int main() {

  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

  Main();

}

#endif



const int MOD = 1e9 + 7;

const int N = 2e5 + 10;

int fac[N], inv[N];



int fpow(int a, int b) {

  int ans = 1;

  for(; b > 0; a = 1ll * a * a % MOD, b >>= 1) {

    if(b & 1) {

      ans = 1ll * ans * a % MOD;

    }

  }

  return ans;

}



void init() {

  fac[0] = 1;

  for(int i = 1; i < N; i++) {

    fac[i] = 1ll * fac[i - 1] * i % MOD;

  }

  inv[N - 1] = fpow(fac[N - 1], MOD - 2);

  for(int i = N - 2; i >= 0; i--) {

    inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;

  }

}



const int INV2 = fpow(2, MOD - 2);



int f(int n) {

  return 1ll * n * (n + 1) % MOD * INV2 % MOD;

}



void Main() {

  init();

  int n, m, k; cin >> n >> m >> k;

  int ans = 1ll * fac[n * m - 2] * inv[k - 2] % MOD * inv[n * m - k] % MOD;

  int c = 0;

  for(int i = 0; i < m; i++) {

    c += 1ll * f(i) * n % MOD * n % MOD;

    if(c >= MOD) c -= MOD;

  }

  for(int i = 0; i < n; i++) {

    c += 1ll * f(i) * m % MOD * m % MOD;

    if(c >= MOD) c -= MOD;

  }

  ans = 1ll * ans * c % MOD;

  cout << ans << "\n";

}


// Faster C++ solution for the same problem (measured speedup: 1.2209422540434074x):
#include <bits/stdc++.h>

#define mm(x,k) memset (x, k, sizeof(x));

#define ll long long

#define ff(i,a,b) for(ll i = a ; i  < b ; ++i)

#define fd(i,a,b) for(ll i = a ; i <= b ; ++i)

using namespace std;

#define mo 1000000007

ll mod(ll a , ll b){

    ll t = 1;

    while(b){

        if(b&1) t = a * t % mo;

        b >>= 1; a = a * a % mo;

    } return t;

}

ll a[200005];

ll C(ll n , ll m){

    return (a[n] * mod(a[n-m],mo-2)) % mo * mod(a[m],mo-2) %mo;

}

int main(){

    a[0] = 1;

    ff(i,1,200005) a[i] = a[i-1] * i % mo;

    ll n , m , k;

    cin >> n >> m >> k;

    cout<< C(n*m,k)*C(k,2)%mo*(n+m)%mo*mod(3,mo-2)%mo;

}