My brute force solution with complexity O(n*n*p*q) ~ 10^12  have got AC. So add test generated by this programm and some similar, please.

#include <stdio.h>

int i, n, p;

int main() {
    n = 5000;
    printf("%d 2\n", n);
    printf("3 3 2 2 3\n");
    printf("4970 4970 2 2 3\n");
    p = 345;
    printf("%d\n", p);
    for (i = 0; i < p; i ++) {
        printf("%d %d %d %d %d %d %d %d %d\n", i+1, n - 2 - i, 1, n - 2, 1, -1, 0, 0, p);
    }
    return 0;
}