
'''simple docstring'''
import functools
import math

import flax.linen as nn
import jax
import jax.numpy as jnp




def 					_UpperCamelCase		(    SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__ = 4096       )   ->				Any:


		'''simple docstring'''


		snake_case       ,snake_case       ,snake_case   :    Tuple			       =		key.shape[-3:]
		snake_case   :    Optional[Any]			       =		value.shape[-1]
		snake_case   :    List[Any]			       =		min(SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__       )
		snake_case   :    Optional[Any]			       =		query / jnp.sqrt(SCREAMING_SNAKE_CASE__       )

		@functools.partial(jax.checkpoint      ,    prevent_cse=SCREAMING_SNAKE_CASE__       )
		def summarize_chunk(SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__       ):
				snake_case   :    Tuple			       =		jnp.einsum('''...qhd,...khd->...qhk'''      ,    SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__      ,    precision=SCREAMING_SNAKE_CASE__       )

				snake_case   :    str			       =		jnp.max(SCREAMING_SNAKE_CASE__      ,    axis=-1      ,    keepdims=SCREAMING_SNAKE_CASE__       )
				snake_case   :    int			       =		jax.lax.stop_gradient(SCREAMING_SNAKE_CASE__       )
				snake_case   :    List[str]			       =		jnp.exp(attn_weights - max_score       )

				snake_case   :    str			       =		jnp.einsum('''...vhf,...qhv->...qhf'''      ,    SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__      ,    precision=SCREAMING_SNAKE_CASE__       )
				snake_case   :    int			       =		jnp.einsum('''...qhk->...qh'''      ,    SCREAMING_SNAKE_CASE__       )

				return (exp_values, exp_weights.sum(axis=-1       ), max_score)

		def chunk_scanner(SCREAMING_SNAKE_CASE__       ):
				# julienne key array
				snake_case   :    Tuple			       =		jax.lax.dynamic_slice(
				    operand=SCREAMING_SNAKE_CASE__      ,    start_indices=[0] * (key.ndim - 3) + [chunk_idx, 0, 0]      ,    slice_sizes=list(key.shape[:-3]       ) + [key_chunk_size, num_heads, k_features]      ,    )

				# julienne value array
				snake_case   :    Optional[int]			       =		jax.lax.dynamic_slice(
				    operand=SCREAMING_SNAKE_CASE__      ,    start_indices=[0] * (value.ndim - 3) + [chunk_idx, 0, 0]      ,    slice_sizes=list(value.shape[:-3]       ) + [key_chunk_size, num_heads, v_features]      ,    )

				return summarize_chunk(SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__       )

		snake_case       ,snake_case       ,snake_case   :    str			       =		jax.lax.map(f=SCREAMING_SNAKE_CASE__      ,    xs=jnp.arange(0      ,    SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__       )       )

		snake_case   :    Optional[Any]			       =		jnp.max(SCREAMING_SNAKE_CASE__      ,    axis=0      ,    keepdims=SCREAMING_SNAKE_CASE__       )
		snake_case   :    int			       =		jnp.exp(chunk_max - global_max       )

		chunk_values *= jnp.expand_dims(SCREAMING_SNAKE_CASE__      ,    axis=-1       )
		chunk_weights *= max_diffs

		snake_case   :    List[str]			       =		chunk_values.sum(axis=0       )
		snake_case   :    str			       =		jnp.expand_dims(SCREAMING_SNAKE_CASE__      ,    -1       ).sum(axis=0       )

		return all_values / all_weights




def 					_UpperCamelCase		(    SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__=jax.lax.Precision.HIGHEST      ,    SCREAMING_SNAKE_CASE__ = 1024      ,    SCREAMING_SNAKE_CASE__ = 4096       )   ->				List[str]:


		'''simple docstring'''


		snake_case       ,snake_case       ,snake_case   :    Tuple			       =		query.shape[-3:]

		def chunk_scanner(SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__       ):
				# julienne query array
				snake_case   :    int			       =		jax.lax.dynamic_slice(
				    operand=SCREAMING_SNAKE_CASE__      ,    start_indices=([0] * (query.ndim - 3)) + [chunk_idx, 0, 0]      ,    slice_sizes=list(query.shape[:-3]       ) + [min(SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__       ), num_heads, q_features]      ,    )

				return (
				    chunk_idx + query_chunk_size,  # unused ignore it
				    _query_chunk_attention(
				        query=SCREAMING_SNAKE_CASE__      ,    key=SCREAMING_SNAKE_CASE__      ,    value=SCREAMING_SNAKE_CASE__      ,    precision=SCREAMING_SNAKE_CASE__      ,    key_chunk_size=SCREAMING_SNAKE_CASE__       ),
				)

		snake_case       ,snake_case   :    Union[str, Any]			       =		jax.lax.scan(
		    f=SCREAMING_SNAKE_CASE__      ,    init=0      ,    xs=SCREAMING_SNAKE_CASE__      ,    length=math.ceil(num_q / query_chunk_size       )       )

		return jnp.concatenate(SCREAMING_SNAKE_CASE__      ,    axis=-3       )  # fuse the chunked result back






class      snake_case__    (	nn.Module ):







		"""simple docstring"""

		lowerCamelCase							=		42
		lowerCamelCase							=		8
		lowerCamelCase							=		64
		lowerCamelCase							=		0.0
		lowerCamelCase							=		False
		lowerCamelCase							=		jnp.floataa



		def 	lowerCAmelCase							(	self							:       Tuple	)		->       Optional[Any]:






				"""simple docstring"""







				snake_case   :    Union[str, Any]			       =		self.dim_head * self.heads
				snake_case   :    Optional[int]			       =		self.dim_head**-0.5

				# Weights were exported with old names {to_q, to_k, to_v, to_out}
				snake_case   :    int			       =		nn.Dense(UpperCamelCase__   ,     use_bias=UpperCamelCase__   ,     dtype=self.dtype   ,     name='''to_q'''	)
				snake_case   :    Union[str, Any]			       =		nn.Dense(UpperCamelCase__   ,     use_bias=UpperCamelCase__   ,     dtype=self.dtype   ,     name='''to_k'''	)
				snake_case   :    Tuple			       =		nn.Dense(UpperCamelCase__   ,     use_bias=UpperCamelCase__   ,     dtype=self.dtype   ,     name='''to_v'''	)

				snake_case   :    Any			       =		nn.Dense(self.query_dim   ,     dtype=self.dtype   ,     name='''to_out_0'''	)
				snake_case   :    Tuple			       =		nn.Dropout(rate=self.dropout	)



		def 	lowerCAmelCase							(	self							:       str   ,     UpperCamelCase__							:       Dict	)		->       Union[str, Any]:






				"""simple docstring"""







				snake_case       ,snake_case       ,snake_case   :    List[str]			       =		tensor.shape
				snake_case   :    Tuple			       =		self.heads
				snake_case   :    int			       =		tensor.reshape(UpperCamelCase__   ,     UpperCamelCase__   ,     UpperCamelCase__   ,     dim // head_size	)
				snake_case   :    int			       =		jnp.transpose(UpperCamelCase__   ,     (0, 2, 1, 3)	)
				snake_case   :    str			       =		tensor.reshape(batch_size * head_size   ,     UpperCamelCase__   ,     dim // head_size	)
				return tensor



		def 	lowerCAmelCase							(	self							:       str   ,     UpperCamelCase__							:       str	)		->       List[Any]:






				"""simple docstring"""







				snake_case       ,snake_case       ,snake_case   :    List[Any]			       =		tensor.shape
				snake_case   :    Optional[Any]			       =		self.heads
				snake_case   :    Optional[int]			       =		tensor.reshape(batch_size // head_size   ,     UpperCamelCase__   ,     UpperCamelCase__   ,     UpperCamelCase__	)
				snake_case   :    Any			       =		jnp.transpose(UpperCamelCase__   ,     (0, 2, 1, 3)	)
				snake_case   :    List[str]			       =		tensor.reshape(batch_size // head_size   ,     UpperCamelCase__   ,     dim * head_size	)
				return tensor



		def __call__(	self							:       List[str]   ,     UpperCamelCase__							:       Dict   ,     UpperCamelCase__							:       Tuple=None   ,     UpperCamelCase__							:       Optional[int]=True	)		->       Tuple:






				"""simple docstring"""







				snake_case   :    Optional[int]			       =		hidden_states if context is None else context

				snake_case   :    Union[str, Any]			       =		self.query(UpperCamelCase__	)
				snake_case   :    List[Any]			       =		self.key(UpperCamelCase__	)
				snake_case   :    List[str]			       =		self.value(UpperCamelCase__	)

				snake_case   :    int			       =		self.reshape_heads_to_batch_dim(UpperCamelCase__	)
				snake_case   :    Optional[Any]			       =		self.reshape_heads_to_batch_dim(UpperCamelCase__	)
				snake_case   :    Optional[Any]			       =		self.reshape_heads_to_batch_dim(UpperCamelCase__	)

				if self.use_memory_efficient_attention:
						snake_case   :    Any			       =		query_states.transpose(1   ,     0   ,     2	)
						snake_case   :    List[str]			       =		key_states.transpose(1   ,     0   ,     2	)
						snake_case   :    List[Any]			       =		value_states.transpose(1   ,     0   ,     2	)

						# this if statement create a chunk size for each layer of the unet
						# the chunk size is equal to the query_length dimension of the deepest layer of the unet

						snake_case   :    Union[str, Any]			       =		query_states.shape[-3]
						if flatten_latent_dim % 64 == 0:
								snake_case   :    List[Any]			       =		int(flatten_latent_dim / 64	)
						elif flatten_latent_dim % 16 == 0:
								snake_case   :    List[str]			       =		int(flatten_latent_dim / 16	)
						elif flatten_latent_dim % 4 == 0:
								snake_case   :    Dict			       =		int(flatten_latent_dim / 4	)
						else:
								snake_case   :    int			       =		int(UpperCamelCase__	)

						snake_case   :    Any			       =		jax_memory_efficient_attention(
						    UpperCamelCase__   ,     UpperCamelCase__   ,     UpperCamelCase__   ,     query_chunk_size=UpperCamelCase__   ,     key_chunk_size=4096 * 4	)

						snake_case   :    Union[str, Any]			       =		hidden_states.transpose(1   ,     0   ,     2	)
				else:
						# compute attentions
						snake_case   :    Tuple			       =		jnp.einsum('''b i d, b j d->b i j'''   ,     UpperCamelCase__   ,     UpperCamelCase__	)
						snake_case   :    List[str]			       =		attention_scores * self.scale
						snake_case   :    str			       =		nn.softmax(UpperCamelCase__   ,     axis=2	)

						# attend to values
						snake_case   :    Dict			       =		jnp.einsum('''b i j, b j d -> b i d'''   ,     UpperCamelCase__   ,     UpperCamelCase__	)

				snake_case   :    Optional[int]			       =		self.reshape_batch_dim_to_heads(UpperCamelCase__	)
				snake_case   :    List[str]			       =		self.proj_attn(UpperCamelCase__	)
				return self.dropout_layer(UpperCamelCase__   ,     deterministic=UpperCamelCase__	)







class      snake_case__    (	nn.Module ):







		"""simple docstring"""

		lowerCamelCase							=		42
		lowerCamelCase							=		42
		lowerCamelCase							=		42
		lowerCamelCase							=		0.0
		lowerCamelCase							=		False
		lowerCamelCase							=		jnp.floataa
		lowerCamelCase							=		False



		def 	lowerCAmelCase							(	self							:       Optional[int]	)		->       Any:






				"""simple docstring"""







				snake_case   :    Dict			       =		FlaxAttention(
				    self.dim   ,     self.n_heads   ,     self.d_head   ,     self.dropout   ,     self.use_memory_efficient_attention   ,     dtype=self.dtype	)
				# cross attention
				snake_case   :    List[Any]			       =		FlaxAttention(
				    self.dim   ,     self.n_heads   ,     self.d_head   ,     self.dropout   ,     self.use_memory_efficient_attention   ,     dtype=self.dtype	)
				snake_case   :    Optional[int]			       =		FlaxFeedForward(dim=self.dim   ,     dropout=self.dropout   ,     dtype=self.dtype	)
				snake_case   :    Any			       =		nn.LayerNorm(epsilon=1e-5   ,     dtype=self.dtype	)
				snake_case   :    str			       =		nn.LayerNorm(epsilon=1e-5   ,     dtype=self.dtype	)
				snake_case   :    Any			       =		nn.LayerNorm(epsilon=1e-5   ,     dtype=self.dtype	)
				snake_case   :    Union[str, Any]			       =		nn.Dropout(rate=self.dropout	)



		def __call__(	self							:       Optional[int]   ,     UpperCamelCase__							:       Any   ,     UpperCamelCase__							:       Dict   ,     UpperCamelCase__							:       List[Any]=True	)		->       List[str]:






				"""simple docstring"""







				snake_case   :    Any			       =		hidden_states
				if self.only_cross_attention:
						snake_case   :    Any			       =		self.attna(self.norma(UpperCamelCase__	)   ,     UpperCamelCase__   ,     deterministic=UpperCamelCase__	)
				else:
						snake_case   :    List[Any]			       =		self.attna(self.norma(UpperCamelCase__	)   ,     deterministic=UpperCamelCase__	)
				snake_case   :    str			       =		hidden_states + residual

				# cross attention
				snake_case   :    Tuple			       =		hidden_states
				snake_case   :    List[str]			       =		self.attna(self.norma(UpperCamelCase__	)   ,     UpperCamelCase__   ,     deterministic=UpperCamelCase__	)
				snake_case   :    List[Any]			       =		hidden_states + residual

				# feed forward
				snake_case   :    Dict			       =		hidden_states
				snake_case   :    int			       =		self.ff(self.norma(UpperCamelCase__	)   ,     deterministic=UpperCamelCase__	)
				snake_case   :    str			       =		hidden_states + residual

				return self.dropout_layer(UpperCamelCase__   ,     deterministic=UpperCamelCase__	)







class      snake_case__    (	nn.Module ):







		"""simple docstring"""

		lowerCamelCase							=		42
		lowerCamelCase							=		42
		lowerCamelCase							=		42
		lowerCamelCase							=		1
		lowerCamelCase							=		0.0
		lowerCamelCase							=		False
		lowerCamelCase							=		False
		lowerCamelCase							=		jnp.floataa
		lowerCamelCase							=		False



		def 	lowerCAmelCase							(	self							:       Any	)		->       Any:






				"""simple docstring"""







				snake_case   :    int			       =		nn.GroupNorm(num_groups=32   ,     epsilon=1e-5	)

				snake_case   :    Union[str, Any]			       =		self.n_heads * self.d_head
				if self.use_linear_projection:
						snake_case   :    int			       =		nn.Dense(UpperCamelCase__   ,     dtype=self.dtype	)
				else:
						snake_case   :    Optional[Any]			       =		nn.Conv(
						    UpperCamelCase__   ,     kernel_size=(1, 1)   ,     strides=(1, 1)   ,     padding='''VALID'''   ,     dtype=self.dtype   ,     )

				snake_case   :    Optional[Any]			       =		[
				    FlaxBasicTransformerBlock(
				        UpperCamelCase__   ,     self.n_heads   ,     self.d_head   ,     dropout=self.dropout   ,     only_cross_attention=self.only_cross_attention   ,     dtype=self.dtype   ,     use_memory_efficient_attention=self.use_memory_efficient_attention   ,     )
				    for _ in range(self.depth	)
				]

				if self.use_linear_projection:
						snake_case   :    Optional[int]			       =		nn.Dense(UpperCamelCase__   ,     dtype=self.dtype	)
				else:
						snake_case   :    List[Any]			       =		nn.Conv(
						    UpperCamelCase__   ,     kernel_size=(1, 1)   ,     strides=(1, 1)   ,     padding='''VALID'''   ,     dtype=self.dtype   ,     )

				snake_case   :    Union[str, Any]			       =		nn.Dropout(rate=self.dropout	)



		def __call__(	self							:       Optional[Any]   ,     UpperCamelCase__							:       List[str]   ,     UpperCamelCase__							:       Any   ,     UpperCamelCase__							:       Any=True	)		->       Tuple:






				"""simple docstring"""







				snake_case       ,snake_case       ,snake_case       ,snake_case   :    str			       =		hidden_states.shape
				snake_case   :    Union[str, Any]			       =		hidden_states
				snake_case   :    Optional[int]			       =		self.norm(UpperCamelCase__	)
				if self.use_linear_projection:
						snake_case   :    Tuple			       =		hidden_states.reshape(UpperCamelCase__   ,     height * width   ,     UpperCamelCase__	)
						snake_case   :    List[str]			       =		self.proj_in(UpperCamelCase__	)
				else:
						snake_case   :    Optional[Any]			       =		self.proj_in(UpperCamelCase__	)
						snake_case   :    List[Any]			       =		hidden_states.reshape(UpperCamelCase__   ,     height * width   ,     UpperCamelCase__	)

				for transformer_block in self.transformer_blocks:
						snake_case   :    List[str]			       =		transformer_block(UpperCamelCase__   ,     UpperCamelCase__   ,     deterministic=UpperCamelCase__	)

				if self.use_linear_projection:
						snake_case   :    int			       =		self.proj_out(UpperCamelCase__	)
						snake_case   :    Any			       =		hidden_states.reshape(UpperCamelCase__   ,     UpperCamelCase__   ,     UpperCamelCase__   ,     UpperCamelCase__	)
				else:
						snake_case   :    Optional[Any]			       =		hidden_states.reshape(UpperCamelCase__   ,     UpperCamelCase__   ,     UpperCamelCase__   ,     UpperCamelCase__	)
						snake_case   :    Any			       =		self.proj_out(UpperCamelCase__	)

				snake_case   :    Dict			       =		hidden_states + residual
				return self.dropout_layer(UpperCamelCase__   ,     deterministic=UpperCamelCase__	)







class      snake_case__    (	nn.Module ):







		"""simple docstring"""

		lowerCamelCase							=		42
		lowerCamelCase							=		0.0
		lowerCamelCase							=		jnp.floataa



		def 	lowerCAmelCase							(	self							:       Union[str, Any]	)		->       Optional[int]:






				"""simple docstring"""







				snake_case   :    Union[str, Any]			       =		FlaxGEGLU(self.dim   ,     self.dropout   ,     self.dtype	)
				snake_case   :    Dict			       =		nn.Dense(self.dim   ,     dtype=self.dtype	)



		def __call__(	self							:       List[Any]   ,     UpperCamelCase__							:       int   ,     UpperCamelCase__							:       Optional[Any]=True	)		->       Union[str, Any]:






				"""simple docstring"""







				snake_case   :    Tuple			       =		self.net_a(UpperCamelCase__   ,     deterministic=UpperCamelCase__	)
				snake_case   :    int			       =		self.net_a(UpperCamelCase__	)
				return hidden_states







class      snake_case__    (	nn.Module ):







		"""simple docstring"""

		lowerCamelCase							=		42
		lowerCamelCase							=		0.0
		lowerCamelCase							=		jnp.floataa



		def 	lowerCAmelCase							(	self							:       Dict	)		->       str:






				"""simple docstring"""







				snake_case   :    Dict			       =		self.dim * 4
				snake_case   :    Dict			       =		nn.Dense(inner_dim * 2   ,     dtype=self.dtype	)
				snake_case   :    Optional[Any]			       =		nn.Dropout(rate=self.dropout	)



		def __call__(	self							:       Tuple   ,     UpperCamelCase__							:       List[str]   ,     UpperCamelCase__							:       List[Any]=True	)		->       Tuple:






				"""simple docstring"""







				snake_case   :    Dict			       =		self.proj(UpperCamelCase__	)
				snake_case       ,snake_case   :    List[str]			       =		jnp.split(UpperCamelCase__   ,     2   ,     axis=2	)
				return self.dropout_layer(hidden_linear * nn.gelu(UpperCamelCase__	)   ,     deterministic=UpperCamelCase__	)




'''simple docstring'''
from __future__ import annotations

import sys




def 					_UpperCamelCase		(    SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__       )   ->				tuple[int, int]:


		'''simple docstring'''


		if abs(SCREAMING_SNAKE_CASE__       ) == 1:
				return a, 0
		elif abs(SCREAMING_SNAKE_CASE__       ) == 1:
				return 0, b

		snake_case       ,snake_case   :    Tuple			       =		a, b
		snake_case       ,snake_case   :    List[str]			       =		1, 0
		snake_case       ,snake_case   :    Optional[Any]			       =		0, 1

		while remainder != 0:
				snake_case   :    int			       =		old_remainder // remainder
				snake_case       ,snake_case   :    Tuple			       =		remainder, old_remainder - quotient * remainder
				snake_case       ,snake_case   :    Optional[Any]			       =		coeff_a, old_coeff_a - quotient * coeff_a
				snake_case       ,snake_case   :    Dict			       =		coeff_b, old_coeff_b - quotient * coeff_b

		# sign correction for negative numbers
		if a < 0:
				snake_case   :    Optional[Any]			       =		-old_coeff_a
		if b < 0:
				snake_case   :    int			       =		-old_coeff_b

		return old_coeff_a, old_coeff_b




def 					_UpperCamelCase		(    )   ->				str:


		'''simple docstring'''


		if len(sys.argv       ) < 3:
				print('''2 integer arguments required'''       )
				return 1
		snake_case   :    str			       =		int(sys.argv[1]       )
		snake_case   :    List[str]			       =		int(sys.argv[2]       )
		print(extended_euclidean_algorithm(SCREAMING_SNAKE_CASE__      ,    SCREAMING_SNAKE_CASE__       )       )
		return 0


if __name__ == "__main__":
						raise SystemExit(main())


