import argparse
import random

def main():
    parser = argparse.ArgumentParser(description="Test generator for Segment Tree problem")
    parser.add_argument('-n', type=int, required=True, help="Size of the array")
    parser.add_argument('-q', type=int, required=True, help="Number of queries")
    parser.add_argument('-s', type=int, default=None, help="Random seed for reproducibility")
    args = parser.parse_args()

    # Apply seed if provided
    if args.s is not None:
        random.seed(args.s)

    n = args.n
    q = args.q

    # Print n and q
    print(f"{n} {q}")

    # Generate and print the initial array
    a = [str(random.randint(0, 10**9)) for _ in range(n)]
    print(" ".join(a))

    # Pre-select some "hot" indices to update/query often
    hot_indices = [random.randint(1, n) for _ in range(max(1, min(5, n)))]

    # Helper function to generate an index with a bias towards "hot" indices
    def get_index():
        if random.random() < 0.2:  # 20% chance to pick a hotspot
            return random.choice(hot_indices)
        return random.randint(1, n)

    # Helper function to generate an interval [l, r] with length biases
    def get_interval():
        prob = random.random()
        if prob < 0.2:
            # 10% chance: Entire array or almost entire array (forces lazy tags at the root)
            l = random.randint(1, max(1, n // 10))
            r = random.randint(min(n, n - n // 10 + 1), n)
        elif prob < 0.4:
            # 20% chance: Very long intervals
            l = random.randint(1, n // 3)
            r = random.randint(2 * (n // 3), n)
        elif prob < 0.6:
            # 10% chance: Tiny intervals (length 1 or 2, tests leaf behavior)
            l = random.randint(1, n)
            r = min(n, l + random.randint(0, 2))
        else:
            # 60% chance: Completely uniform interval
            l = random.randint(1, n)
            r = random.randint(1, n)
        
        # Ensure l <= r
        if l > r:
            l, r = r, l
        
        return max(1, l), min(n, r)

    # Generate the queries
    for _ in range(q):
        # 1: Point Update, 2: Range Update, 3: Range Query
        # We can bias the query types (e.g., more updates than queries to build lazy tags)
        q_type = random.choices([1, 2, 3], weights=[20, 40, 40], k=1)[0]
        
        if q_type == 1:
            x = get_index()
            v = random.randint(0, 10**9)
            print(f"1 {x} {v}")
            
        elif q_type == 2:
            l, r = get_interval()
            v = random.randint(0, 10**9)
            print(f"2 {l} {r} {v}")
            
        elif q_type == 3:
            l, r = get_interval()
            print(f"3 {l} {r}")

if __name__ == "__main__":
    main()
