Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

The only difference between easy and hard versions is constraints. Nauuo is a girl who…

  1. User

    The only difference between easy and hard versions is constraints.

    Nauuo is a girl who loves random picture websites.

    One day she made a random picture website by herself which includes n pictures.

    When Nauuo visits the website, she sees exactly one picture. The website does not display each picture with equal probability. The i-th picture has a non-negative weight w_i, and the probability of the i-th picture being displayed is \frac{w_i}{∑_{j=1}^nw_j}. That is to say, the probability of a picture to be displayed is proportional to its weight.

    However, Nauuo discovered that some pictures she does not like were displayed too often.

    To solve this problem, she came up with a great idea: when she saw a picture she likes, she would add 1 to its weight; otherwise, she would subtract 1 from its weight.

    Nauuo will visit the website m times. She wants to know the expected weight of each picture after all the m visits modulo 998244353. Can you help her?

    The expected weight of the i-th picture can be denoted by \frac {q_i} {p_i} where \gcd(p_i,q_i)=1, you need to print an integer r_i satisfying 0≤ r_i<998244353 and r_i⋅ p_i≡ q_i\pmod{998244353}. It can be proved that such r_i exists and is unique. Input

    The first line contains two integers n and m (1≤ n≤ 2⋅ 10^5, 1≤ m≤ 3000) — the number of pictures and the number of visits to the website.

    The second line contains n integers a_1,a_2,…,a_n (a_i is either 0 or 1) — if a_i=0 , Nauuo does not like the i-th picture; otherwise Nauuo likes the i-th picture. It is guaranteed that there is at least one picture which Nauuo likes.

    The third line contains n positive integers w_1,w_2,…,w_n (w_i ≥ 1) — the initial weights of the pictures. It is guaranteed that the sum of all the initial weights does not exceed 998244352-m.

    Output

    The output contains n integers r_1,r_2,…,r_n — the expected weights modulo 998244353.

    Examples

    Input

    2 1 0 1 2 1

    Output

    332748119 332748119

    Input

    1 2 1 1

    Output

    3

    Input

    3 3 0 1 1 4 3 5

    Output

    160955686 185138929 974061117

    Note

    In the first example, if the only visit shows the first picture with a probability of \frac 2 3, the final weights are (1,1); if the only visit shows the second picture with a probability of \frac1 3, the final weights are (2,2).

    So, both expected weights are \frac2 3⋅ 1+\frac 1 3⋅ 2=\frac4 3 .

    Because 332748119⋅ 3≡ 4\pmod{998244353}, you need to print 332748119 instead of \frac4 3 or 1.3333333333.

    In the second example, there is only one picture which Nauuo likes, so every time Nauuo visits the website, w_1 will be increased by 1.

    So, the expected weight is 1+2=3.

    Nauuo is very naughty so she didn't give you any hint of the third example.

  2. DeepSeek Assistant

    We need to compute expected weight after m steps for each i. There is a classic problem of expected weight evolution with probability proportional to weights and updates +1 or -1 based on like/dislike. Constraints: n up to 2e5, m up to 3000. We need O(n * m?) maybe O(n + m^2) or something. Since m is only 3000, we can compute DP over total weight? The process: each visit, a picture i is selected with probability proportional to its current weight. Then we update: if a_i = 1 (like), w_i += 1; else (dislike) w_i -= 1. Weight cannot go below 0? Actually w_i positive initially, and maybe can become 0? They didn't say that weights stay positive; but they said "weight" could become zero or negative? But typically in such problems, they might treat weight as non-negative? However the process could cause weight to become negative? But initial weights are positive, and after many steps of dislikes, could go negative. However constraints guarantee sum of initial weights <= 998244352 - m, maybe to avoid overflow modulo? Not exactly. It's typical for probability distribution; but if weight becomes negative, probability proportional to negative weight would be nonsense. So we must assume that weight never becomes negative. The process updates by subtracting 1 from disliked pictures, but if a picture is disliked and weight is 1, subtract 1 becomes 0. At zero, it could still be selected? The probability would be zero because weight zero. So if it becomes zero, it remains zero forever because future visits never select it (since weight 0) and it never gets incremented (because it's disliked, only decrement when selected). Actually if it becomes zero, then it cannot be selected because weight zero => probability zero; so it stays zero forever. So that's fine. Similarly, weight could become negative if we subtract 1 from zero? But if weight is zero, probability of selection is 0, so it will never be selected, so it stays zero. So the process effectively keeps weights non-negative. Initially positive; they can become zero. So we can assume weights are non-negative.

    Goal: Expected weight after m steps. The expectation over random selection paths.

    Observation: The process is a kind of Pólya's urn-like but with both additions and deletions. Not symmetric, but we can try to compute expected weights using linearity of expectation and maybe coupling with total sum and maybe probabilities.

    Let W_i(t) be random weight of picture i after t steps, t=0,...,m. Initially W_i(0)=w_i known.

    At each step t+1, pick a picture j with probability proportional to its current weight: P(j) = W_j(t) / S(t) where S(t) = sum_{k} W_k(t). Then update: if a_j = 1: W_j(t+1) = W_j(t)+1; else: W_j(t+1) = W_j(t)-1 (but ensuring non-negative? we assume it doesn't become negative; but if it's zero, it's not selected. So fine). For other i != j, W_i(t+1) = W_i(t).

    We need E[W_i(m)].

    Because of linearity, maybe we can derive recursions for expectations. However note that the probabilities depend on current weights, so it's not linear.

    But m up to 3000, n up to 2e5, we need efficient method.

    We can consider grouping liked and disliked pictures. Since the update rule depends only on like/dislike, the system might be treatable by analyzing total weight of liked and disliked sets separately, and individual expectations as scaling with initial weights. Because the selection probability is proportional to weight, and the update adds or subtracts 1, which affects the total sum differently: liked increases total sum by 1, disliked decreases total sum by 1. So total sum S(t) evolves: S(t+1) = S(t) + Δ where Δ = +1 if selected liked, -1 if selected disliked. So S(t) is a random process.

    Expectation of W_i(t) may be expressed as w_i times some factor plus something? Let's attempt to derive formulas.

    Let L = set of liked pictures (a_i=1), D = disliked (a_i=0). Denote total liked weight at time t: L(t) = sum_{i∈L} W_i(t), total disliked weight: D(t)= sum_{i∈D} W_i(t). Then S(t) = L(t)+D(t). At each step, probability of selecting a liked picture = L(t)/S(t). If liked selected, L(t) increases by 1 (since that picture weight increases by 1, so L(t) increments by 1), D(t) unchanged. So L(t+1) = L(t)+1, D(t+1)=D(t), S(t+1)=S(t)+1. If disliked selected, then D(t) decreases by 1 (the disliked picture weight decreases by 1), L(t) unchanged. So L(t+1)=L(t), D(t+1)=D(t)-1, S(t+1)=S(t)-1. But note: if a disliked picture has weight 1 and gets selected, it becomes 0; D decreases by 1. That's consistent. So total sum S evolves as random walk with step ±1 with probabilities based on current L(t)/S(t). However, S(t) might change, but L and D are also random.

    We might consider expected values over time. But because of state-dependence, it's complicated.

    Since m is only 3000, we might use DP over the total sum or some aggregated parameters, but n is large. Could it be that the expected weight of each picture i is equal to w_i times something plus something based on whether it is liked or disliked? Possibly due to linearity and symmetry within groups. Because the system is symmetric among pictures with the same like/dislike and same initial weight? But initial weights can be arbitrary, so not symmetric. However, maybe the evolution of each weight is proportional to its weight? Let's hypothesize: The process is such that the ratios of weights within each group (liked or disliked) remain constant? Not exactly: for liked pictures, if selected, that particular picture's weight increases by 1, breaking the ratio. For disliked pictures, when selected, that picture's weight decreases by 1, also breaking ratio. So not constant.

    But we might still compute expected values using linearity: consider the contribution of each initial weight and each step's increments/decrements.

    We can think of writing W_i(m) = w_i + sum_{t=0}^{m-1} X_{i,t}, where X_{i,t} is indicator (or ±1) if picture i is selected at step t and its like/dislike gives +1 for like, -1 for dislike. Actually if at step t, we select picture j, then we add Δ_j = (1 if j liked else -1) to W_j(t+1). But note: that change persists to future steps. So W_i(m) = w_i + sum_{t=0}^{m-1} (Δ_i * I{ picture i selected at step t }). However careful: The selection at step t uses the state at time t, which depends on prior selections. So the events are not independent. But the sum representation is correct: each time picture i is selected, its weight changes by Δ_i (Δ_i = 1 if liked, -1 if disliked). So total change to weight i = Δ_i * (number of times picture i is selected up to time m-1). Let N_i be the number of times picture i is selected during the m steps. Then final weight = w_i + Δ_i * N_i. But note: if picture i is disliked and its weight becomes zero, it might be selected again? If weight zero, selection probability is zero, so it cannot be selected after it becomes zero. However the representation w_i + Δ_i * N_i would still hold, because each time it is selected, it loses 1; but if it becomes zero, it cannot be selected later. That's consistent because N_i would stop increasing once weight is zero? Actually if weight is zero, the probability of selection is zero, so it won't be selected further, so N_i would be finite. But does the equation w_i + Δ_i * N_i equal the final weight? If Δ_i = -1, each selection reduces weight by 1, but if weight hits zero, further selections would be impossible; but if by some hypothetical selection while weight zero, it would go to -1, but that doesn't happen. So the formula holds: final weight = w_i + N_i * Δ_i. However N_i is the actual number of selections, which is limited by the fact that once weight hits zero, selection probability is zero; but it's still correct that final weight is w_i - N_i. But if N_i > w_i initially, final weight would be negative, but that can't happen because we cannot have more selections than weight allows. So N_i is bounded by w_i when Δ_i = -1. The process ensures that N_i <= w_i initially (plus maybe increments from likes? But if disliked, there are no increments, so indeed N_i ≤ w_i). So we can still write.

    Thus E[W_i(m)] = w_i + Δ_i * E[N_i].

    So the problem reduces to computing expected number of times picture i is selected over m steps. The process is a sequential random selection with state-dependent probabilities.

    Now, the expected number of selections might be computed via linearity: E[N_i] = sum_{t=0}^{m-1} P( picture i selected at step t ). So we need to compute probability that at step t, the selection picks i. That probability depends on the distribution of weights at time t, which is random. So we need to compute for each t the expectation of (W_i(t) / S(t)). Because conditional on state, the probability of picking i is W_i(t)/S(t). So P(i selected at step t) = E[ W_i(t) / S(t) ]. So we need to compute E[ W_i(t) / S(t) ] for t=0,...,m-1. Not straightforward due to fraction.

    However we can attempt to compute expected values of some ratios using dynamic programming on total sum and maybe total liked sum? But there are many pictures.

    Given m ≤ 3000, we might attempt to compute these expectations via a DP over the number of liked selections and disliked selections? Because the process depends only on total liked and total disliked? Actually the probability of selecting a liked picture at any step depends on L(t)/S(t) and the selection among liked pictures is then proportional to individual weights. However, if we condition on the sequence of which group (liked or disliked) is selected at each step, the distribution within the group might be manageable.

    Alternative approach: Consider the whole process as a two-step: first, the total sum and the total liked weight evolve; then within liked group, the selection probabilities are proportional to weights, and similarly for disliked. But since the updates only affect the selected picture, they affect the composition of the group.

    We can think of using a "martingale" or "exchangeability" property: the process is similar to a Polya's urn where each picture has a "type" (like/dislike) and each time we pick a ball (picture) with probability proportional to weight, we then add or remove weight from that ball. Could be modeled as a Markov process.

    Because m is relatively small, we can compute the joint distribution of the weights? Not possible due to high dimension.

    But maybe we can compute expected weight of each picture using linearity of expectation and a trick: define potentials or use generating functions.

    I recall a known Codeforces problem: "Nauuo and Pictures" or similar. Indeed there is CF problem 1527C? Actually there is "Nauuo and Pictures" from a contest. Might be problem "1172B? No. There is "Nauuo and Pictures" from Codeforces Round #564? Actually I recall a problem: "Nauuo and Pictures (hard version)" with constraints n up to 2e5, m up to 3000, and solution uses DP on the number of liked and disliked selections. Yes, it's a known problem: "Nauuo and Pictures". The solution: Separate liked and disliked pictures. Compute expected weight for each picture as:

    E[final weight_i] = w_i * f(s, t) + g(s, t) (or something) depending on if liked or disliked.

    More specifically, I remember that one can compute DP for the total sum of weights and total liked sum. Then for each liked picture, the expectation is proportional to its initial weight; for each disliked picture, expectation is also proportional but with a shift.

    Let's derive.

    Define: Let A = sum of initial weights of liked pictures: L0 = sum_{i∈L} w_i. Let B = sum of initial weights of disliked pictures: D0 = sum_{i∈D} w_i. Total S0 = A + B.

    During the process, let total steps m. The evolution of the total liked weight and total disliked weight are dependent. But maybe we can compute expectations of L(t) and D(t). However, individual expectations might be expressed in terms of L(t) and w_i. For liked pictures: For each liked picture i, the expected weight at time t might be w_i times something like E[ S(t) / S0? Not exactly.

    Consider the following: For liked pictures, each time a liked picture is selected, its weight increases. This is reminiscent of a reinforcement process. Possibly the relative ratios within liked group are preserved in expectation? Let's test with small case. Suppose two liked pictures with weights w1, w2. Process: When liked picture selected, its weight increases by 1. The selection among liked is proportional to weights. This is like a Polya's urn: starting with balls of two colors, each time we pick a ball, we add a ball of the same color. But here we add weight (increment by 1) instead of adding a new ball; but it's analogous to a Polya's urn with the number of balls replaced by weight. Actually in classic Polya's urn, each ball is counted, and we add one ball of the same color. The probability of picking a color is proportional to its number of balls. The expected proportion of balls of each color is constant (martingale). In our process, for liked pictures, if we ignore disliked ones, the selection among liked is proportional to weight, and when selected, weight increases by 1 (like adding a ball). This suggests that within the liked group, the ratio of weights among liked pictures remains a martingale? That is, the fraction W_i(t) / L(t) might be a martingale? Let's check: If we condition on current state, when a liked picture j is selected, W_j increases by 1, L increases by 1. So the new ratio for i ≠ j: W_i/(L+1) vs old W_i/L. For j: (W_j+1)/(L+1) vs old W_j/L. Let's compute expected change of W_i/L.

    Given that the next step picks a liked picture with probability L/S, and among liked picks i with probability W_i/L. But also picks a disliked picture with probability D/S; then L unchanged, and W_i unchanged. So the expected next ratio:

    E[W_i(t+1)/L(t+1) | state] =

    If liked selected: probability L/S. Then if i is the selected liked: prob W_i/L => new ratio = (W_i+1)/(L+1). If liked but j≠i selected: prob (L - W_i)/L? Actually sum over j≠i with probability W_j/L => new ratio = W_i/(L+1) because L becomes L+1 and W_i unchanged. So contribution from liked: (L/S) * [ (W_i/L)(W_i+1)/(L+1) + sum_{j≠i} (W_j/L) * (W_i/(L+1)) ] = (L/S) * [ (W_i/L)(W_i+1)/(L+1) + ((L-W_i)/L)(W_i/(L+1)) ] = (L/S) * [ (W_i/(L+1))( (W_i+1)/L? Wait combine:

    Actually compute term by term:

    • If liked and i selected: probability (L/S)*(W_i/L) = W_i/S. Then ratio = (W_i+1)/(L+1).
    • If liked and some other liked j ≠ i selected: probability (L/S)*((L-W_i)/L) = (L-W_i)/S. Then ratio = W_i/(L+1) (since L increments but W_i unchanged).
    • If disliked selected (any disliked): probability D/S. Then L unchanged, so L(t+1)=L, W_i unchanged, ratio = W_i/L.

    Thus expected ratio:

    E = (W_i/S) * (W_i+1)/(L+1) + ((L-W_i)/S) * W_i/(L+1) + (D/S) * W_i/L.

    Simplify: first two terms together: (W_i/(S*(L+1))) * (W_i+1) + ((L-W_i)/S) * W_i/(L+1) = [W_i/(S*(L+1))] * (W_i+1) + [W_i (L-W_i)]/(S*(L+1)). Sum = W_i/(S*(L+1)) * ( (W_i+1) + (L-W_i) ) = W_i/(S*(L+1)) * (L+1) = W_i/S.

    So E = W_i/S + (D/S) * W_i/L = W_i/S + W_i * D/(S L) = W_i/S * (1 + D/L) = W_i/S * ( (L+D)/L ) = W_i/S * (S/L) = W_i/L.

    Thus indeed E[W_i(t+1)/L(t+1) | state] = W_i(t)/L(t). So the ratio is a martingale! Similarly, for disliked pictures? Let's check for a disliked picture i: ratio W_i/D? But when a disliked picture is selected, D decreases by 1, and W_i decreases by 1. That might not preserve the martingale property? Let's compute.

    For disliked pictures, we consider fraction W_i/D. State: L, D, S = L+D. When a disliked picture j is selected: D decreases by 1 (to D-1). If j = i, then W_i decreases by 1. So new ratio: (W_i-1)/(D-1). If j ≠ i, W_i unchanged, D becomes D-1, so ratio = W_i/(D-1). When liked picture selected: D unchanged, W_i unchanged, so ratio = W_i/D.

    Now compute expected next ratio given state.

    Probabilities: liked selected: L/S. Then ratio = W_i/D.

    Disliked selected: D/S. Among disliked, probability i is selected: W_i/D => ratio = (W_i-1)/(D-1). Probability other disliked selected: (D - W_i)/D => ratio = W_i/(D-1).

    Thus expected:

    E = (L/S)(W_i/D) + (D/S)[ (W_i/D)( (W_i-1)/(D-1) ) + ((D-W_i)/D)( W_i/(D-1) ) ].

    Second term: (D/S) * (1/D) * [ W_i*(W_i-1)/(D-1) + (D-W_i)W_i/(D-1) ] = (1/S) * [ W_i(W_i-1) + W_i*(D-W_i) ]/(D-1) = (1/S) * [ W_i*( (W_i-1)+(D-W_i) ) ]/(D-1) = (1/S) * [ W_i*(D-1) ]/(D-1) = W_i/S.

    So E = (L/S)*(W_i/D) + W_i/S = W_i/S * ( L/D + 1 ) = W_i/S * ( (L+D)/D ) = W_i/S * (S/D) = W_i/D.

    Thus the ratio W_i/D for disliked pictures is also a martingale! Nice!

    Therefore, for each liked picture, the process for the fraction of its weight among total liked is a martingale. For each disliked picture, the fraction among total disliked is a martingale.

    Because it's a martingale, its expectation remains constant over time, equal to initial value. So for t≥0:

    E[ W_i(t) / L(t) ] = w_i / L0 (if i liked) E[ W_i(t) / D(t) ] = w_i / D0 (if i disliked)

    But careful: D(t) can be zero? Initially D0 > 0? Not necessarily; there could be no disliked pictures? However input guarantees at least one liked picture, but could be zero disliked? Possibly D0=0. If D0=0, then disliked set empty; we don't need to consider them. But if D0>0, D(t) may eventually become zero? Possibly if all disliked weights become zero. In that case, D(t)=0, then the ratio W_i/D is undefined. However, the martingale property holds as long as D(t)>0. If D(t)=0, then no disliked pictures left, and process from then on only selects liked pictures. But before that, the martingale might still hold in expectation? However we can treat that case with care. Since m ≤ 3000 and initial D0 can be up to maybe 998244352, but D0 is sum of weights of disliked pictures. It is positive if any disliked picture exists. It could become zero only if we subtract from disliked pictures enough times to bring total sum to zero. But D(t) is non-negative integer. It can become zero. In that case, after that, no further selections from disliked, and the disliked pictures remain zero. However, we need expectations. Possibly we can still use the martingale property if we define conditional expectations and handle zero via continuity? However maybe we can avoid by using generating functions or DP that accounts for possibility of D becoming zero. But note that if D0=0, the problem is trivial: only liked pictures, and each step increases total weight by 1, and probability of selecting i is proportional to its weight. For liked pictures, the ratios W_i/L are martingale, so expectation of final weight can be computed. So we'll assume that we can use the martingale property for all t as long as we condition on D(t)>0? But expectations unconditional over all paths can be computed via taking expectations over positive events; but if D(t)=0, the ratio W_i/D is undefined. However we may not need to directly compute E[W_i/D] for disliked pictures after D=0 because after that point, W_i are zero (since D=0 means all disliked weights zero, each individual disliked weight zero as well). Actually if D(t)=0, then each disliked picture must have weight 0 because sum of non-negative weights is zero. So W_i(t)=0 for all disliked i. Then ratio would be 0/0 undefined. But we could define it as something? However maybe we can compute expected weight for disliked pictures using another approach: The martingale property holds for all times if we define the ratio to be constant on the event where denominator is zero? Not straightforward.

    But perhaps we can avoid using the ratio for disliked in that way: Instead of using W_i/D, we could use something like W_i/(D + constant) to avoid zero. However maybe we can rely on the fact that D(t) > 0 for all t up to m with high probability? Not necessarily; it can become zero. But m is up to 3000 and D0 may be large or small. We need exact modular arithmetic, so we need to handle that possibility exactly.

    Alternate approach: Use DP to compute expected values of L(t) and maybe also something like "inverse of S(t)"? Actually we can compute expected values of certain rational functions by using dynamic programming over number of liked and disliked selections. Because the process is Markov over (L, D) (total liked weight, total disliked weight) only! Wait, is the state fully described by (L, D)? If we know total liked weight and total disliked weight, can we determine the distribution of individual weights? Possibly not, but we may be able to compute expectations of W_i(t) given these totals? Because for liked pictures, we have the martingale: E[W_i(t) | history]? Actually the martingale property gives that the conditional expectation of W_i(t)/L(t) given the past is constant. More precisely, for liked pictures, the process Z_i(t) = W_i(t)/L(t) is a martingale with respect to the natural filtration. This implies that for any stopping time, E[Z_i(t)] = initial. In particular, E[W_i(t)] = E[ L(t) * Z_i(t) ] = w_i/L0 * E[L(t)] because Z_i(t) and L(t) are not independent but we can use the tower property? Actually, we have E[W_i(t)] = E[ L(t) * (W_i(t)/L(t)) ] = E[ L(t) * Z_i(t) ]. Since Z_i(t) is a martingale, but it's not independent of L(t). However we can use law of total expectation: E[W_i(t)] = E[ E[ W_i(t) | L(t) ]? But that would require conditional distribution of W_i(t) given L(t). However, due to the martingale property, we can maybe derive that E[W_i(t)] = (w_i/L0) * E[L(t)]? Let's test: If Z_i(t) is a martingale, then E[Z_i(t)] = w_i/L0. But does it imply that E[L(t) Z_i(t)] = E[L(t)] * E[Z_i(t)]? Not generally, unless L(t) and Z_i(t) are uncorrelated. But they might be correlated. However maybe the linearity holds because of exchangeability? Consider all liked pictures: they are symmetric except for initial weights. The total liked weight L(t) is sum of W_i(t) over liked i. Then the expected value of W_i(t) given the total and the initial weights? Since the evolution within liked group is like a Polya's urn, the expected proportion of each liked picture given total L(t) might be equal to its initial proportion? Actually in Polya's urn, the proportions are a martingale, but the joint distribution is such that the expected weight of a specific ball given total is its initial proportion times total? Let's check: In a Polya's urn where each time we pick a ball of a color and add one ball of the same color, the number of balls of each color is not independent, but the expected number of balls of a given color given the total number of balls is indeed proportional to its initial number? Not exactly: The conditional expectation of the number of balls of a given color given the total number of balls is random because the proportion is random. However the unconditional expectation E[number of balls] can be computed via linearity. But we need E[W_i(t)] directly.

    Alternatively, we might use linearity of expectation with indicator approach: E[W_i(t)] = w_i + Δ_i * sum_{k=0}^{t-1} E[W_i(k)/S(k)]. So if we can compute E[W_i(k)/S(k)], we could sum. And we have relation W_i(k)/S(k) = (W_i(k)/L(k)) * (L(k)/S(k)) for liked pictures, and similarly for disliked. So E[W_i(k)/S(k)] = E[ (W_i(k)/L(k)) * (L(k)/S(k)) ]. Since W_i(k)/L(k) and L(k)/S(k) are not independent, we need joint expectations.

    But maybe we can compute the expected value of some functions like L(k) and S(k) directly via DP, and also the expectations of products like (W_i(k)/L(k)) * (L(k)/S(k)). Because W_i(k)/L(k) is a martingale with expectation w_i/L0, and L(k)/S(k) is also a martingale? Let's test if L(k)/S(k) is a martingale.

    Compute E[L(t+1)/S(t+1) | state]. Use similar method. When liked selected: L→L+1, S→S+1 => new ratio = (L+1)/(S+1). When disliked selected: L unchanged, S→S-1 => new ratio = L/(S-1). Probabilities: liked: L/S, disliked: D/S.

    So E = (L/S)*(L+1)/(S+1) + (D/S)L/(S-1). Compute: first term = L(L+1) / (S(S+1)). Second term = D L / (S(S-1)). This is not obviously equal to L/S. Let's test with numbers: suppose L=1, D=1, S=2. Then L/S=0.5. Compute first term: (1/2)(2/3)=1/3≈0.333. Second term: (1/2)*1/(1)=0.5. Sum=0.833? That's not 0.5. So L/S is not a martingale. Indeed, the process tends to increase liked proportion over time because liked pictures increase weight, disliked decrease.

    So we need to handle correlations.

    Given constraints, perhaps we can compute expected weights using DP over number of liked selections and disliked selections. Since m ≤ 3000, the total number of liked selections (let's denote x) and disliked selections (y) such that x + y = m, but the order matters because probabilities depend on current L and D. However we can consider the process solely in terms of L and D, which follow a Markov chain: Starting from (L0, D0). At each step, the probability to go to (L+1, D) is L/(L+D); probability to go to (L, D-1) is D/(L+D). (But careful: when a disliked picture is selected, D decreases by 1. However if D=0, then probability is 0, but we never have D=0? Actually D could become zero, then only liked selections occur, and L increases by 1 each step. But we can handle that as absorbing state? If D=0, then from that point on, only liked selections happen, and L increases deterministically each step. But we could still treat it as a Markov chain with probabilities as above, with the rule that if D=0, then probability of disliked selection is 0, and liked selection happens with probability 1, leading to L+1. So we can simulate the DP on (L,D) states that are reachable within m steps. Since L0+D0 can be up to ~1e9? Actually sum of initial weights can be up to 998244352 - m, which is about 1e9. But L and D are large numbers, cannot DP over their values directly. However the number of steps m is only 3000, so the changes in L and D are at most m. So we can consider the offsets: let L = L0 + a, D = D0 - b, where a is number of liked selections, b is number of disliked selections. But note: liked selections increase L by 1; disliked selections decrease D by 1. So after some steps, we have a (≥0) liked selections and b (≥0) disliked selections, but they are not independent because total steps = a+b, and also we cannot have b exceed D0 because D can't go negative? Actually D can go to zero but not negative. So b ≤ D0. But D0 could be large, so b is at most m (since we only have m steps), so b ≤ m ≤ 3000. So D will be D0 - b, which is still huge but we care about probabilities that depend on ratios L/(L+D). That ratio involves large numbers L0 + a and D0 - b. So we can compute probabilities of sequences of steps using a DP that tracks a and b and multiplies probabilities that depend on L and D at each step. The probabilities are rational functions of L0, D0, a, b. Since m is only 3000, we can compute the probability of each pair (a,b) such that a+b = m (or less if D becomes zero early? Actually if D becomes zero before m steps, then b = D0 (all disliked weights used up) and the remaining steps will all be liked selections. So we need to consider paths where D hits zero before m steps. That means b can be less than the number of steps that are disliked selections? Actually b is the total number of disliked selections that occur over the m steps. Since each disliked selection reduces D by 1, and D cannot go negative, the maximum number of disliked selections possible is min(D0, m). But if D0 < m, then after D0 disliked selections, D becomes 0, and from then on only liked selections occur. So for the whole m steps, we will have a liked selections and b disliked selections, with a+b = m, and b ≤ D0. But if D0 < m, b can be at most D0, and a = m - b. So b can range from max(0, m - something)? Actually the process always continues: even if D=0, we still have liked selections with probability 1. So the number of disliked selections b can be any integer from 0 to min(D0, m). So we need to compute probability distribution over b (or (a,b)) given the process.

    Now, if we know the probability of ending with a liked selections and b disliked selections, we could compute expected final weight for a picture i? Possibly because conditioned on the counts (a,b), the distribution of individual weights might be simpler? Actually if we condition on the entire sequence of which group (liked or disliked) is selected at each step, but not which specific picture within the group, then the process inside each group evolves as a Polya's urn conditioned on the total number of selections from that group. Specifically, for liked pictures, given that there are a selections of liked pictures over the m steps (in some order interspersed with disliked selections), the evolution of liked pictures is like: we start with weights w_i (i∈L). Each time a liked picture is selected (which occurs at certain times), we increase its weight by 1. The probability of selecting a particular liked picture at each such step is proportional to its current weight. This is exactly a generalized Polya's urn: starting with initial weights (w_i). After a selections (each time we pick a ball proportionally to weight and add 1 to that ball's weight). The final distribution of weights after a such steps is known: the expected weight of each liked picture is w_i * ( (S0+L_increase?) Actually, we might compute expected weight after a selections ignoring the disliked selections? But careful: the disliked selections interleave with liked selections and affect the total sum S, which affects the probability of selecting a liked picture? However, given that we know at which steps a liked selection occurred (the order among liked selections and the times they occur, and also that between liked selections there may be disliked selections that change D and thus S), does that affect the distribution of liked weights? For liked selections, the probability of picking a particular liked picture at a liked selection step depends only on the current weights of liked pictures and the total sum S(t). The total sum S(t) at that time includes both L(t) and D(t). The probability for liked selection is (W_i(t) / S(t)), but conditional on the event that the selection is from the liked group, the probability of picking i is (W_i(t) / L(t)). Because given that the selected picture is liked, the conditional probability is proportional to W_i among liked. Indeed, the unconditional probability of selecting liked picture i is (W_i(t)/S(t)). The probability that the selected picture is liked (any liked) is L(t)/S(t). So the conditional probability that it's i given it's liked is (W_i(t)/S(t)) / (L(t)/S(t)) = W_i(t)/L(t). So, when a liked selection occurs, the specific liked picture chosen is chosen with probability proportional to its current weight among liked pictures, independent of D(t) (since D(t) cancels). Therefore, the evolution of liked pictures when a liked selection occurs depends only on the current liked weights, not on D(t). The times between liked selections do not affect the liked weights, because during disliked selections, liked weights remain unchanged. So given that there are exactly a liked selections in total, the distribution of liked picture weights after all steps depends only on the order of these a selections and the initial weights, and is independent of when they occur relative to disliked selections. Moreover, the process of selecting among liked pictures is exactly a Polya's urn where each selection adds 1 to the chosen liked picture. After a selections, the expected weight of liked picture i? Since each selection adds 1 to the chosen picture, the total added weight to liked pictures is a. The Polya urn with initial weights (w_i) and a additions: each addition picks a liked picture with probability proportional to current weight. This is equivalent to sampling without replacement? Actually it's like the following: The probability that the k-th liked selection picks picture i is proportional to its weight at that time. This is the same as the Chinese restaurant process? But we can compute expected weight after a steps: It is known that the expected weight after a steps is w_i * ( (total initial liked weight + a) / total initial liked weight )? Let's test with simple case: Suppose we have two liked pictures with initial weights w1, w2, and we do a steps of adding 1 each time to the selected picture (proportional to weight). Is the expected final weight of picture 1 equal to w1 * ( (w1+w2 + a) / (w1+w2) )? Not exactly, because the expected increment each step is proportional to its current expected weight divided by total liked weight. But since the increments affect future probabilities, there might be a linearity. Let's compute using martingale: For liked pictures, we have martingale Z_i = W_i/L. So E[Z_i(final)] = w_i/L0. Also L(final) = L0 + a (since each liked selection adds 1 to L, and disliked selections do not change L). So L(final) is deterministic given a (a = number of liked selections). But careful: L(final) is exactly L0 + a, because each liked selection increases L by 1, and disliked selections do not affect L. So L(final) is not random; it's determined by the number of liked selections (which is random overall, but conditional on a, it's fixed). So conditional on a (number of liked selections), we have L(final) = L0 + a. Then we have E[W_i(final) | a] = E[ L(final) * Z_i(final) | a ] = (L0 + a) * E[Z_i(final) | a]. But is Z_i(final) independent of a? Not necessarily. However, the martingale property holds unconditionally, but conditional on a, the distribution might be different. However we can use the fact that Z_i is a martingale with respect to the filtration that includes the sequence of selections. The event of having exactly a liked selections is a stopping time? The total number of liked selections up to step m is not a stopping time in the sense that it depends on the whole process up to time m. But we can condition on the whole path of group selections. Actually, the process within liked group given the number of liked selections a: the sequence of liked selections is a process where at each liked selection step, we pick a liked picture proportionally to its current weight. This is exactly a Polya's urn with a draws. And it is known that the expected weight after a steps is w_i * ( (L0 + a) / L0 )? Let's check with a simple simulation or compute expectation directly using induction.

    Consider a liked set. Suppose we perform k selections, each time picking a liked picture with probability proportional to its current weight, and then incrementing its weight by 1. Let L_k be total liked weight after k selections (starting L0). Then L_k = L0 + k. For a specific picture i, we can compute E[W_i(k)]. We can derive recurrence: At step, if we pick i with probability W_i / L, then W_i becomes W_i+1; else W_i unchanged (if another liked picture is picked). But note that the selection is only among liked pictures; there are no disliked interferences. So the evolution is Markov on liked weights.

    We can write: E[W_i(k+1) | state] = W_i + (W_i / L) * 1? Actually, after a selection, W_i increases by 1 if i is selected; otherwise unchanged. So conditional on current weights, the expected new W_i is W_i + (W_i / L). So unconditional expectation satisfies: E[W_i(k+1)] = E[ W_i(k) + W_i(k)/L(k) ]. But L(k) = L0 + k, deterministic? Actually L(k) is total liked weight after k selections, which is deterministic: L(k) = L0 + k. However W_i(k) is random. But we have relationship: sum_i W_i(k) = L(k) deterministic? Yes, because total liked weight after k selections is initial L0 plus k (since each liked selection adds 1 to total liked weight). So L(k) is deterministic given k. That's key! In the liked-only process, total liked weight after each liked selection is deterministic: L_k = L0 + k. Because each liked selection increases total liked weight by exactly 1, and there are no other changes. Therefore, even though the distribution of individual weights is random, their sum is fixed. That simplifies expectation: Because L(k) is deterministic, we can write E[W_i(k)] = ? We have the recurrence:

    E[W_i(k+1)] = E[ W_i(k) + (W_i(k) / L(k)) ] because probability of picking i at step k+1 (given current state) is W_i(k)/L(k). Since L(k) is deterministic constant = L0 + k, we can write:

    E[W_i(k+1)] = E[W_i(k)] + (1/(L0+k)) E[W_i(k)].

    Thus we have a linear recurrence: E[W_i(k+1)] = (1 + 1/(L0+k)) E[W_i(k)].

    Therefore, E[W_i(k)] = w_i * ∏{t=0}^{k-1} (1 + 1/(L0 + t)) = w_i * ∏{t=0}^{k-1} ( (L0 + t + 1)/(L0 + t) ) = w_i * ( (L0 + k) / L0 ).

    Thus E[W_i(k)] = w_i * (L0 + k)/L0.

    Great! So in the liked-only process after exactly k liked selections, the expected weight of liked picture i is proportional to its initial weight scaled by the factor (L0+k)/L0. That's neat.

    Now, in our full process, the liked pictures also experience disliked selections interspersed, but those do not affect liked weights. However, the number of liked selections a is random and may depend on the process. But we can condition on a and use the above result, because given that there are exactly a liked selections (and the exact times they occur), the distribution of final liked weights is the same as the liked-only process with a selections (since the disliked selections don't affect liked weights). However, does the presence of disliked selections affect the conditional distribution of liked weights given a? The liked weights only change during liked selections, and during those selections, the probability of picking a particular liked picture is proportional to its weight at that time. But does the fact that disliked selections occur between liked selections affect the distribution of liked weights at the times of liked selections? Liked weights are unchanged during disliked selections, so the state of liked weights before a liked selection is exactly the same as if all previous liked selections had occurred contiguously, with no disliked selections in between. Since disliked selections do not modify liked weights, the evolution of liked weights across liked selections is independent of the timing and of the existence of disliked selections. Therefore, conditional on the number of liked selections a, the distribution of final liked weights is exactly the same as that of the liked-only process with a selections. So we have:

    E[W_i(final) | a] = w_i * (L0 + a) / L0, for i liked.

    Now, for disliked pictures, we can perform a similar analysis. For disliked pictures, total disliked weight after b disliked selections? However, note that disliked selections decrease the total disliked weight by 1 each time a disliked picture is selected. So after b disliked selections, the total disliked weight becomes D0 - b (since each reduces total disliked weight by 1). But careful: D can become zero before we have performed b selections if D0 < b, but b cannot exceed D0 because we cannot have more disliked selections than initial total disliked weight? Actually we can have more? Suppose D0 = 5, we could have more than 5 disliked selections? Each disliked selection reduces D by 1, but if D reaches 0, further disliked selections cannot occur because probability of selecting a disliked picture becomes 0. So the number of disliked selections b is at most D0. So b ≤ D0. So D(final) = D0 - b.

    Now, consider the process for disliked pictures conditioned on there being exactly b disliked selections. During each disliked selection, the specific disliked picture chosen is selected with probability proportional to its current weight among disliked pictures at that time. When a disliked picture is selected, its weight decreases by 1. This is like a reverse urn: starting with weights w_i for i∈D. At each step, we pick a disliked picture with probability proportional to its current weight, and then subtract 1 from its weight. The total disliked weight reduces by 1 each step. This process is analogous to sampling without replacement? We can attempt to compute expected weight after b such steps.

    Let D(b) be total disliked weight after b steps (deterministic: D0 - b). For a specific disliked picture i, we can derive recurrence similar to liked but with subtraction. Suppose we have performed k disliked selections so far, and we are about to perform the (k+1)-th. At that point, total disliked weight is D0 - k (deterministic). The probability that picture i is selected given current weights is W_i(k) / (D0 - k). If selected, its weight becomes W_i(k)-1; otherwise unchanged. So expected next weight: E[W_i(k+1) | state] = W_i(k) - (W_i(k) / (D0 - k)). Thus unconditional expectation satisfies:

    E[W_i(k+1)] = E[W_i(k)] - (1/(D0 - k)) E[W_i(k)] = (1 - 1/(D0 - k)) E[W_i(k)].

    Therefore, E[W_i(k)] = w_i * ∏{t=0}^{k-1} (1 - 1/(D0 - t)) = w_i * ∏{t=0}^{k-1} ((D0 - t - 1)/(D0 - t)) = w_i * ( (D0 - k) / D0 ).

    Thus E[W_i(k)] = w_i * (D0 - k) / D0 = w_i * (D0 - k)/D0.

    That's for exactly k disliked selections (and no liked selections interfering). But does the presence of liked selections affect this? Disliked selections happen at certain times, but between them, liked selections occur. During liked selections, disliked weights remain unchanged. So the evolution of disliked weights during disliked selections is independent of the timing: the state before a disliked selection is exactly what it would be if all previous disliked selections had occurred contiguously, because liked selections do not affect disliked weights. Therefore, conditional on the number of disliked selections b, the distribution of final disliked weights is the same as the disliked-only process with b selections. So we have:

    For i disliked, E[W_i(final) | b] = w_i * (D0 - b) / D0, provided b ≤ D0. If b > D0, probability zero.

    But careful: In the disliked-only process, we assumed that each selection decreases weight by 1, and weights remain non-negative. The formula E[W_i(b)] = w_i * (D0 - b)/D0 works as long as b ≤ D0. For b > D0, it's impossible because total disliked weight cannot become negative. So indeed b ≤ D0.

    Thus we have conditional expectations:

    If i liked: E[W_i | a] = w_i * (L0 + a) / L0. If i disliked: E[W_i | b] = w_i * (D0 - b) / D0, where b = number of disliked selections.

    But note that a and b are related: a + b = m, but only if D0 is sufficiently large such that D never hits zero before m steps? Actually, if D0 ≥ m, then it's possible that b ranges from 0 to m. But if D0 < m, then b cannot exceed D0, and a = m - b, but also the process must have exactly b disliked selections (≤ D0). In any case, a + b = m because each step either increases L (liked selection) or decreases D (disliked selection). However, if D becomes zero earlier, then for the remaining steps only liked selections occur. So still a + b = m, with b ≤ D0. So indeed the total number of liked selections a = m - b.

    Thus, overall unconditional expected weight for liked picture i:

    E[W_i] = w_i/L0 * E[ L0 + a ] = w_i/L0 * (L0 + E[a])? Not exactly because a is random and we have conditional expectation linear in a. Since E[W_i | a] = w_i * (L0 + a)/L0 = w_i + (w_i/L0) * a, we have:

    E[W_i] = w_i + (w_i/L0) * E[a].

    Similarly for disliked picture i:

    E[W_i | b] = w_i * (D0 - b)/D0 = w_i - (w_i/D0) * b.

    Thus E[W_i] = w_i - (w_i/D0) * E[b] (provided b ≤ D0 always, which holds because b ≤ D0 with probability 1). So we need E[a] or E[b] (since a = m - b, E[a] = m - E[b]).

    So the problem reduces to computing the expected number of disliked selections (or liked selections) over the m steps. Because the conditional expectations are linear in a or b, and we have derived that regardless of the order, the conditional expected weight for each picture given the total counts is linear. But we must verify that the derivation holds even when D0 is small and D hits zero early? In that case, b cannot exceed D0, and our conditional expectation formula for disliked pictures when b = D0 yields 0? Because w_i * (D0 - D0)/D0 = 0. That matches: if all disliked weight is removed, each disliked picture weight becomes 0. But is that always the case? If D0 < m, then after D0 disliked selections, D becomes 0, and all disliked weights become 0. Then further steps only liked selections, so final disliked weights are 0. Our formula with b = D0 gives 0. So consistent. And if b < D0 (i.e., some disliked weight remains), then formula gives positive expected weight. But note: The conditional expectation we derived for disliked pictures given b assumes that b disliked selections have occurred, and the distribution of final disliked weights is the same as the disliked-only process with b selections. However, if b < D0 but D0 is finite, the process could have some disliked pictures become zero earlier? For example, a disliked picture with small initial weight could become zero before b total selections, but the formula w_i*(D0 - b)/D0 yields an expectation that might be less than zero? Actually it's positive as long as D0 - b > 0. But expectation should be non-negative. But could a picture become zero earlier and then never be selected again, leading to its final weight maybe zero even though total b selections are less than D0? But the expectation we derived from the recurrence assumes that after b selections (each decreasing total weight by 1), the expected weight of picture i is w_i * (D0 - b)/D0. But is that correct even if some pictures may have hit zero early? Let's test with a simple case: D0=2, two disliked pictures both with weight 1. b=1. The disliked-only process: We start with weights (1,1). After one selection, total disliked becomes 1. Which picture is selected? Probability 1/2 each. If selected, its weight becomes 0; the other remains 1. So final weights: (0,1) or (1,0). Expected weights: (0.5, 0.5). Our formula gives w_i*(D0-b)/D0 = 1*(2-1)/2 = 0.5. So correct. Now consider D0=3, pictures with weights (2,1). b=2. Let's compute expected weight of first picture. D0=3, b=2, formula says 2*(3-2)/3 = 2/3 ≈0.6667. Let's simulate disliked-only: start (2,1). First selection: pick first with prob 2/3, then weights become (1,1); pick second with prob 1/3, weights become (2,0). Then second selection: From state (1,1): total=2; pick first with prob 1/2 => (0,1); pick second => (1,0). So from first selection first, final weights: (0,1) with prob (2/3)(1/2)=1/3; (1,0) with prob (2/3)(1/2)=1/3. From first selection second: state (2,0) but second picture weight 0, so total=2; only first picture can be selected (prob 1). It becomes (1,0). So final weights: (1,0) with prob 1/3. So overall, first picture weight: 0 with prob 1/3, 1 with prob 2/3? Actually from first selection first: two outcomes: (0,1) and (1,0). So first weight=0 prob 1/3, =1 prob 1/3? Wait careful: After first selection first, we have (1,1). Second selection: if pick first => (0,1): first weight 0; if pick second => (1,0