No-Edge Pizza

Interview

Time limit1sMemory limit512 MB

Summary

Track toppings on a circle of N slices; for each order, report whether every residue class mod l has one flavor and the minimum l-window sum.

Level: Medium5 of 10
Topics: Hash map, Math, Implementation
Solved: No attempts yet

Problem

A pizza is round, so it has no edge. Junhyeok runs No-Edge Pizza, a shop named after this idea. No-Edge Pizza sells a special pizza made of $N$ slices. The slices are numbered 1 to $N$ clockwise. Slice $N$ and slice 1 are adjacent. Each slice may have a topping, and a topping's flavor is a positive integer at most $10^9$ . No-Edge Pizza also takes special orders, where the customer chooses the position and flavor of the toppings directly. There are $Q$ special orders in total. For each special order, Junhyeok fills every slice without a special topping with toppings of his choice to finish the pizza.

Junhyeok has three unusual rules for his cooking. First, a customer must eat $l$ consecutive slices at once. Second, the sum of the topping flavors on those $l$ slices must be the same for every possible set of $l$ consecutive slices. Third, $N$ slices split into groups of $l$ must leave no slice over, so $N$ is always a multiple of $l$ . A slice without a topping has flavor 0, and each slice holds at most one topping. Junhyeok makes a pizza only when he can satisfy these rules. When he can make one, he minimizes the sum of the topping flavors on $l$ slices to keep the ingredient cost down.

Help Junhyeok check, for each special order, whether he can make a suitable pizza.

Input

The first line contains $N$ , $l$ , and the number of orders $Q$ , separated by spaces. $(1 \leq l \leq N \leq 1,000,000,000, 1 \leq Q \leq 100,000$ , and $N$ is always divisible by $l)$

Each of the next $Q$ lines contains one request in one of the following forms.

1 $x$ $t$ : Adds a topping with flavor $t$ to slice $x$ . $(1 \leq x \leq N, 1 \leq t \leq 1,000,000,000)$ If slice $x$ already has a topping, removes it and replaces it with a topping of flavor $t$ .

2 $x$ : Removes the topping from slice $x$ . The problem guarantees that slice $x$ has a topping. $(1 \leq x \leq N)$

Output

For each order, print one line. If the order can be accepted, add the toppings first, then print YES and the minimum possible sum of topping flavors over $l$ consecutive slices. If the order cannot be accepted, print NO.

Examples2

Example 1

Input

Expected output

YES 1
YES 10
YES 9
YES 11
NO
YES 11
NO
YES 11
YES 9
YES 0

Example 2

Input

Expected output

YES 4
YES 0
YES 10
NO
YES 8
YES 5
YES 7
YES 5
YES 0
YES 9