身份验证 (Passport)
身份验证 (Passport)
Passport 是最受欢迎的 node.js 身份验证库，在社区中广为人知，并在许多生产应用中成功使用。使用 @nestjs/passport 模块将这个库与 Nest 应用集成非常简单。在高层次上，Passport 执行一系列步骤来：
- 通过验证用户的"凭据"（如用户名/密码、JSON Web Token (JWT)，或来自身份提供商的身份令牌）来验证用户身份
- 管理已验证状态（通过发放便携式令牌，如 JWT，或创建 Express session）
- 将已验证用户的信息附加到
Request对象上，以便在路由处理程序中进一步使用
Passport 拥有丰富的策略生态系统，实现了各种身份验证机制。虽然概念简单，但可供选择的 Passport 策略数量庞大，提供了很多变化。Passport 将这些不同的步骤抽象为标准模式，而 @nestjs/passport 模块将这种模式包装并标准化为熟悉的 Nest 构造。
在本章中，我们将使用这些强大而灵活的模块为 RESTful API 服务器实现完整的身份验证解决方案。您可以使用这里描述的概念来实现任何 Passport 策略以自定义您的身份验证方案。您可以按照本章中的步骤来构建这个完整的示例。您可以在这里找到一个完整工作示例的存储库。
身份验证要求
让我们详细说明我们的要求。对于这个用例，客户端将首先使用用户名和密码进行身份验证。一旦通过身份验证，服务器将发放一个 JWT，该 JWT 可以在后续请求中作为授权标头中的承载令牌发送，以证明身份验证。我们还将创建一个受保护的路由，只有包含有效 JWT 的请求才能访问。
我们将从第一个要求开始：验证用户身份。然后我们将通过发放 JWT 来扩展它。最后，我们将创建一个受保护的路由，检查请求中的有效 JWT。
首先我们需要安装所需的包。Passport 提供了一个名为 passport-local 的策略，它实现了用户名/密码身份验证机制，这符合我们用例这部分的需求。
$ npm install --save @nestjs/passport passport passport-local
$ npm install --save-dev @types/passport-local
info 注意 对于您选择的任何 Passport 策略，您总是需要
@nestjs/passport和passport包。然后，您需要安装特定于策略的包（例如，passport-jwt或passport-local），它实现您正在构建的特定身份验证策略。此外，您还可以安装任何 Passport 策略的类型定义，如上面显示的@types/passport-local，它在编写 TypeScript 代码时提供帮助。
实现 Passport 策略
我们现在准备实现身份验证功能。我们将从任何 Passport 策略使用的过程概述开始。将 Passport 视为一个迷你框架本身是有帮助的。框架的优雅之处在于它将身份验证过程抽象为几个基本步骤，您可以根据正在实现的策略进行自定义。它就像一个框架，因为您通过提供自定义参数（作为普通 JSON 对象）和回调函数形式的自定义代码来配置它，Passport 在适当的时候调用这些代码。@nestjs/passport 模块将这个框架包装在 Nest 风格的包中，使其易于集成到 Nest 应用中。我们将在下面使用 @nestjs/passport，但首先让我们了解原生 Passport 是如何工作的。
在原生 Passport 中，您通过提供两样东西来配置策略：
- 特定于该策略的一组选项。例如，在 JWT 策略中，您可能提供一个用于签名令牌的密钥。
- 一个"验证回调"，这是您告诉 Passport 如何与您的用户存储（您管理用户账户的地方）交互的地方。在这里，您验证用户是否存在（和/或创建新用户），以及他们的凭据是否有效。Passport 库期望这个回调在验证成功时返回完整的用户，如果失败则返回 null（失败定义为用户未找到，或者在 passport-local 的情况下，密码不匹配）。
使用 @nestjs/passport，您通过扩展 PassportStrategy 类来配置 Passport 策略。您通过在子类中调用 super() 方法来传递策略选项（上面的第 1 项），可选择传入选项对象。您通过在子类中实现 validate() 方法来提供验证回调（上面的第 2 项）。
我们将首先生成一个 AuthModule，并在其中生成一个 AuthService：
$ nest g module auth
$ nest g service auth
当我们实现 AuthService 时，我们会发现将用户操作封装在 UsersService 中很有用，所以让我们现在生成该模块和服务：
$ nest g module users
$ nest g service users
将这些生成文件的默认内容替换为如下所示。对于我们的示例应用，UsersService 只是维护一个硬编码的内存用户列表，以及一个按用户名检索用户的查找方法。在真实应用中，这是您使用您选择的库（例如，TypeORM、Sequelize、Mongoose 等）构建用户模型和持久层的地方。
@@filename(users/users.service)
import { Injectable } from '@nestjs/common';
// This should be a real class/interface representing a user entity
export type User = any;
@Injectable()
export class UsersService {
private readonly users = [
{
userId: 1,
username: 'john',
password: 'changeme',
},
{
userId: 2,
username: 'maria',
password: 'guess',
},
];
async findOne(username: string): Promise<User | undefined> {
return this.users.find(user => user.username === username);
}
}
在 UsersModule 中，唯一需要的更改是将 UsersService 添加到 @Module 装饰器的 exports 数组中，以便它在此模块外部可见（我们很快将在 AuthService 中使用它）。
@@filename(users/users.module)
import { Module } from '@nestjs/common';
import { UsersService } from './users.service';
@Module({
providers: [UsersService],
exports: [UsersService],
})
export class UsersModule {}
我们的 AuthService 的工作是检索用户并验证密码。我们为此目的创建一个 validateUser() 方法。在下面的代码中，我们使用方便的 ES6 展开运算符在返回用户对象之前从中剥离密码属性。我们稍后将从 Passport 本地策略调用 validateUser() 方法。
@@filename(auth/auth.service)
import { Injectable } from '@nestjs/common';
import { UsersService } from '../users/users.service';
@Injectable()
export class AuthService {
constructor(private usersService: UsersService) {}
async validateUser(username: string, pass: string): Promise<any> {
const user = await this.usersService.findOne(username);
if (user && user.password === pass) {
const { password, ...result } = user;
return result;
}
return null;
}
}
warning 警告 当然，在真实应用中，您不会以明文形式存储密码。您会使用像 bcrypt 这样的库，使用加盐的单向哈希算法。使用这种方法，您只会存储哈希密码，然后将存储的密码与传入密码的哈希版本进行比较，因此永远不会以明文形式存储或暴露用户密码。为了保持我们的示例应用简单，我们违反了这个绝对要求并使用明文。不要在您的真实应用中这样做！
现在，我们更新 AuthModule 以导入 UsersModule。
@@filename(auth/auth.module)
import { Module } from '@nestjs/common';
import { AuthService } from './auth.service';
import { UsersModule } from '../users/users.module';
@Module({
imports: [UsersModule],
providers: [AuthService],
})
export class AuthModule {}
实现 Passport local
现在我们可以实现我们的 Passport 本地身份验证策略。在 auth 文件夹中创建一个名为 local.strategy.ts 的文件，并添加以下代码：
@@filename(auth/local.strategy)
import { Strategy } from 'passport-local';
import { PassportStrategy } from '@nestjs/passport';
import { Injectable, UnauthorizedException } from '@nestjs/common';
import { AuthService } from './auth.service';
@Injectable()
export class LocalStrategy extends PassportStrategy(Strategy) {
constructor(private authService: AuthService) {
super();
}
async validate(username: string, password: string): Promise<any> {
const user = await this.authService.validateUser(username, password);
if (!user) {
throw new UnauthorizedException();
}
return user;
}
}
我们遵循了前面描述的所有 Passport 策略的配方。在我们使用 passport-local 的用例中，没有配置选项，所以我们的构造函数只是调用 super() 而不传递选项对象。
info 提示 我们可以在
super()调用中传递选项对象来自定义 passport 策略的行为。在这个例子中，passport-local 策略默认期望请求体中有名为username和password的属性。传递选项对象来指定不同的属性名称，例如：super({ usernameField: 'email' })。
我们还实现了 validate() 方法。对于每个策略，Passport 将使用适当的特定于策略的参数集调用验证函数（在 @nestjs/passport 中使用 validate() 方法实现）。对于本地策略，Passport 期望一个具有以下签名的 validate() 方法：validate(username: string, password:string): any。
大部分验证工作在我们的 AuthService 中完成（在 UsersService 的帮助下），所以这个方法非常简单。任何 Passport 策略的 validate() 方法都将遵循类似的模式，只是在凭据如何表示的细节上有所不同。如果找到用户且凭据有效，则返回用户，以便 Passport 可以完成其任务（例如，在 Request 对象上创建 user 属性），请求处理管道可以继续。如果未找到，我们抛出异常并让我们的异常层处理它。
通常，每个策略的 validate() 方法中唯一的重大差异是如何确定用户是否存在且有效。例如，在 JWT 策略中，根据要求，我们可能评估解码令牌中携带的 userId 是否与我们用户数据库中的记录匹配，或者是否与撤销令牌列表匹配。因此，这种子类化和实现特定于策略的验证模式是一致的、优雅的和可扩展的。
我们需要配置 AuthModule 以使用我们刚刚定义的 Passport 功能。更新 auth.module.ts 如下所示：
@@filename(auth/auth.module)
import { Module } from '@nestjs/common';
import { AuthService } from './auth.service';
import { UsersModule } from '../users/users.module';
import { PassportModule } from '@nestjs/passport';
import { LocalStrategy } from './local.strategy';
@Module({
imports: [UsersModule, PassportModule],
providers: [AuthService, LocalStrategy],
})
export class AuthModule {}
内置 Passport Guards
Guards 章节描述了 Guards 的主要功能：确定请求是否将由路由处理程序处理。这仍然是正确的，我们很快就会使用这个标准功能。但是，在使用 @nestjs/passport 模块的上下文中，我们还将引入一个可能起初令人困惑的轻微新变化，所以让我们现在讨论一下。考虑到从身份验证角度来看，您的应用可以存在于两种状态：
- 用户/客户端未登录（未经身份验证）
- 用户/客户端已登录（已经身份验证）
在第一种情况下（用户未登录），我们需要执行两个不同的功能：
- 限制未经身份验证的用户可以访问的路由（即，拒绝访问受限路由）。我们将使用 Guards 的熟悉功能来处理这个功能，通过在受保护的路由上放置 Guard。正如您可能预期的那样，我们将在这个 Guard 中检查有效 JWT 的存在，所以我们稍后会在开始发放 JWT 后处理这个 Guard。
- 当先前未经身份验证的用户尝试登录时启动身份验证步骤本身。这是我们将向有效用户发放 JWT 的步骤。考虑一下这个问题，我们知道我们需要
POST用户名/密码凭据来启动身份验证，所以我们将设置一个POST /auth/login路由来处理这个问题。这引出了一个问题：我们究竟如何在该路由中调用 Passport 本地策略？
答案很简单：通过使用另一种稍微不同类型的 Guard。@nestjs/passport 模块为我们提供了一个内置的 Guard 来做这件事。这个 Guard 调用 Passport 策略并启动上述步骤（检索凭据、运行验证函数、创建用户属性等）。
上面列举的第二种情况（已登录用户）只是依赖于我们已经讨论过的标准类型的 Guard 来为已登录用户启用对受保护路由的访问。
登录路由
有了策略，我们现在可以实现一个基本的 /auth/login 路由，并应用内置的 Guard 来启动 passport-local 流程。
打开 app.controller.ts 文件并将其内容替换为以下内容：
@@filename(app.controller)
import { Controller, Request, Post, UseGuards } from '@nestjs/common';
import { AuthGuard } from '@nestjs/passport';
@Controller()
export class AppController {
@UseGuards(AuthGuard('local'))
@Post('auth/login')
async login(@Request() req) {
return req.user;
}
}
使用 @UseGuards(AuthGuard('local'))，我们使用了 @nestjs/passport 在我们扩展 passport-local 策略时自动提供的 AuthGuard。让我们分解一下。我们的 Passport 本地策略有一个默认名称 'local'。我们在 @UseGuards() 装饰器中引用该名称，将其与 passport-local 包提供的代码关联。这用于消除在我们的应用中有多个 Passport 策略时要调用哪个策略的歧义（每个策略都可能提供特定于策略的 AuthGuard）。虽然我们目前只有一个这样的策略，但我们很快会添加第二个，所以这对于消除歧义是必需的。
为了测试我们的路由，我们现在让 /auth/login 路由简单地返回用户。这也让我们演示另一个 Passport 功能：Passport 根据我们 validate() 方法的返回值自动创建一个 user 对象，并将其作为 req.user 分配给 Request 对象。稍后，我们将用创建并返回 JWT 的代码替换这个。
由于这些是 API 路由，我们将使用常用的 cURL 库来测试它们。您可以使用 UsersService 中硬编码的任何 user 对象进行测试。
$ # POST to /auth/login
$ curl -X POST http://localhost:3000/auth/login -d '{"username": "john", "password": "changeme"}' -H "Content-Type: application/json"
$ # result -> {"userId":1,"username":"john"}
虽然这有效，但直接将策略名称传递给 AuthGuard() 会在代码库中引入魔术字符串。相反，我们建议创建您自己的类，如下所示：
@@filename(auth/local-auth.guard)
import { Injectable } from '@nestjs/common';
import { AuthGuard } from '@nestjs/passport';
@Injectable()
export class LocalAuthGuard extends AuthGuard('local') {}
现在，我们可以更新 /auth/login 路由处理程序并使用 LocalAuthGuard：
@UseGuards(LocalAuthGuard)
@Post('auth/login')
async login(@Request() req) {
return req.user;
}
JWT 功能
我们准备转向身份验证系统的 JWT 部分。让我们回顾并完善我们的要求：
- 用户使用用户名/密码进行身份验证，并返回 JWT（我们已经部分完成了这个，因为我们有用户名/密码部分工作，只需要返回 JWT）
- 创建基于有效 JWT 作为承载令牌存在而受保护的 API 路由
我们需要安装更多包来支持我们的 JWT 要求：
$ npm install --save @nestjs/jwt passport-jwt
$ npm install --save-dev @types/passport-jwt
@nestjs/jwt 包（更多信息请参见这里）是一个帮助 JWT 操作的实用程序包。passport-jwt 包是实现 JWT 策略的 Passport 包，@types/passport-jwt 提供 TypeScript 类型定义。
让我们仔细看看 POST /auth/login 请求是如何处理的。我们使用 passport-local 策略提供的内置 AuthGuard 装饰了路由。这意味着：
- 路由处理程序只有在用户已被验证时才会被调用
req参数将包含一个user属性（在 passport-local 身份验证流程中由 Passport 填充）
考虑到这一点，我们现在终于可以生成真正的 JWT，并在这个路由中返回它。为了保持我们的服务清晰分离，我们将在 AuthService 中处理生成 JWT。打开 auth 文件夹中的 auth.service.ts 文件，添加 login() 方法，并导入 JwtService，如下所示：
@@filename(auth/auth.service)
import { Injectable } from '@nestjs/common';
import { UsersService } from '../users/users.service';
import { JwtService } from '@nestjs/jwt';
@Injectable()
export class AuthService {
constructor(
private usersService: UsersService,
private jwtService: JwtService
) {}
async validateUser(username: string, pass: string): Promise<any> {
const user = await this.usersService.findOne(username);
if (user && user.password === pass) {
const { password, ...result } = user;
return result;
}
return null;
}
async login(user: any) {
const payload = { username: user.username, sub: user.userId };
return {
access_token: this.jwtService.sign(payload),
};
}
}
我们使用 @nestjs/jwt 库，它提供了一个 sign() 函数来从用户对象属性的子集生成我们的 JWT，然后我们将其作为具有单个 access_token 属性的简单对象返回。注意：我们选择属性名称 sub 来保存我们的 userId 值，以与 JWT 标准保持一致。不要忘记将 JwtService 提供者注入到 AuthService 中。
我们现在需要更新 AuthModule 以导入新的依赖项并配置 JwtModule。
首先，在 auth 文件夹中创建 constants.ts，并添加以下代码：
@@filename(auth/constants)
export const jwtConstants = {
secret: 'DO NOT USE THIS VALUE. INSTEAD, CREATE A COMPLEX SECRET AND KEEP IT SAFE OUTSIDE OF YOUR SOURCE CODE.',
};
我们将使用它在 JWT 签名和验证步骤之间共享我们的密钥。
warning 警告 不要公开暴露这个密钥。我们在这里这样做是为了清楚代码在做什么，但在生产系统中您必须使用适当的措施保护这个密钥，如密钥保险库、环境变量或配置服务。
现在，打开 auth 文件夹中的 auth.module.ts 并更新它如下所示：
@@filename(auth/auth.module)
import { Module } from '@nestjs/common';
import { AuthService } from './auth.service';
import { LocalStrategy } from './local.strategy';
import { UsersModule } from '../users/users.module';
import { PassportModule } from '@nestjs/passport';
import { JwtModule } from '@nestjs/jwt';
import { jwtConstants } from './constants';
@Module({
imports: [
UsersModule,
PassportModule,
JwtModule.register({
secret: jwtConstants.secret,
signOptions: { expiresIn: '60s' },
}),
],
providers: [AuthService, LocalStrategy],
exports: [AuthService],
})
export class AuthModule {}
我们使用 register() 配置 JwtModule，传入配置对象。有关 Nest JwtModule 的更多信息请参见这里，有关可用配置选项的更多详细信息请参见这里。
现在我们可以更新 /auth/login 路由以返回 JWT。
@@filename(app.controller)
import { Controller, Request, Post, UseGuards } from '@nestjs/common';
import { LocalAuthGuard } from './auth/local-auth.guard';
import { AuthService } from './auth/auth.service';
@Controller()
export class AppController {
constructor(private authService: AuthService) {}
@UseGuards(LocalAuthGuard)
@Post('auth/login')
async login(@Request() req) {
return this.authService.login(req.user);
}
}
让我们继续使用 cURL 再次测试我们的路由。您可以使用 UsersService 中硬编码的任何 user 对象进行测试。
$ # POST to /auth/login
$ curl -X POST http://localhost:3000/auth/login -d '{"username": "john", "password": "changeme"}' -H "Content-Type: application/json"
$ # result -> {"access_token":"eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9..."}
$ # Note: above JWT truncated
实现 Passport JWT
我们现在可以解决我们的最终要求：通过要求请求中存在有效的 JWT 来保护端点。Passport 也可以在这里帮助我们。它提供了 passport-jwt 策略，用于使用 JSON Web Tokens 保护 RESTful 端点。首先在 auth 文件夹中创建一个名为 jwt.strategy.ts 的文件，并添加以下代码：
@@filename(auth/jwt.strategy)
import { ExtractJwt, Strategy } from 'passport-jwt';
import { PassportStrategy } from '@nestjs/passport';
import { Injectable } from '@nestjs/common';
import { jwtConstants } from './constants';
@Injectable()
export class JwtStrategy extends PassportStrategy(Strategy) {
constructor() {
super({
jwtFromRequest: ExtractJwt.fromAuthHeaderAsBearerToken(),
ignoreExpiration: false,
secretOrKey: jwtConstants.secret,
});
}
async validate(payload: any) {
return { userId: payload.sub, username: payload.username };
}
}
使用我们的 JwtStrategy，我们遵循了前面描述的所有 Passport 策略的相同配方。这个策略需要一些初始化，所以我们通过在 super() 调用中传入选项对象来做到这一点。您可以在这里阅读更多关于可用选项的信息。在我们的情况下，这些选项是：
jwtFromRequest：提供从Request中提取 JWT 的方法。我们将使用在 API 请求的 Authorization 标头中提供承载令牌的标准方法。其他选项在这里描述。ignoreExpiration：为了明确起见，我们选择默认的false设置，它将确保 JWT 未过期的责任委托给 Passport 模块。这意味着如果我们的路由提供了过期的 JWT，请求将被拒绝并发送401 Unauthorized响应。Passport 为我们自动方便地处理这个。secretOrKey：我们使用提供对称密钥来签名令牌的便捷选项。其他选项，如 PEM 编码的公钥，可能更适合生产应用（有关更多信息，请参见这里）。无论如何，如前所述，不要公开暴露这个密钥。
validate() 方法值得一些讨论。对于 jwt-strategy，Passport 首先验证 JWT 的签名并解码 JSON。然后它调用我们的 validate() 方法，将解码的 JSON 作为其单个参数传递。基于 JWT 签名的工作方式，我们保证接收到我们之前签名并发放给有效用户的有效令牌。
因此，我们对 validate() 回调的响应是微不足道的：我们只是返回一个包含 userId 和 username 属性的对象。再次回想一下，Passport 将基于我们 validate() 方法的返回值构建一个 user 对象，并将其作为属性附加到 Request 对象上。
还值得指出的是，这种方法为我们留下了空间（"钩子"）来将其他业务逻辑注入到过程中。例如，我们可以在 validate() 方法中进行数据库查找以提取有关用户的更多信息，从而在我们的 Request 中提供更丰富的 user 对象。这也是我们可能决定进行进一步令牌验证的地方，例如在撤销令牌列表中查找 userId，使我们能够执行令牌撤销。我们在示例代码中实现的模型是一个快速的"无状态 JWT"模型，其中每个 API 调用都基于有效 JWT 的存在立即授权，并且关于请求者的少量信息（其 userId 和 username）在我们的 Request 管道中可用。
将新的 JwtStrategy 作为提供者添加到 AuthModule 中：
@@filename(auth/auth.module)
import { Module } from '@nestjs/common';
import { AuthService } from './auth.service';
import { LocalStrategy } from './local.strategy';
import { JwtStrategy } from './jwt.strategy';
import { UsersModule } from '../users/users.module';
import { PassportModule } from '@nestjs/passport';
import { JwtModule } from '@nestjs/jwt';
import { jwtConstants } from './constants';
@Module({
imports: [
UsersModule,
PassportModule,
JwtModule.register({
secret: jwtConstants.secret,
signOptions: { expiresIn: '60s' },
}),
],
providers: [AuthService, LocalStrategy, JwtStrategy],
exports: [AuthService],
})
export class AuthModule {}
通过导入我们签名 JWT 时使用的相同密钥，我们确保 Passport 执行的验证阶段和 AuthService 执行的签名阶段使用公共密钥。
最后，我们定义 JwtAuthGuard 类，它扩展了内置的 AuthGuard：
@@filename(auth/jwt-auth.guard)
import { Injectable } from '@nestjs/common';
import { AuthGuard } from '@nestjs/passport';
@Injectable()
export class JwtAuthGuard extends AuthGuard('jwt') {}
实现受保护的路由和 JWT 策略守卫
我们现在可以实现我们的受保护路由及其关联的 Guard。
打开 app.controller.ts 文件并更新它，如下所示：
@@filename(app.controller)
import { Controller, Get, Request, Post, UseGuards } from '@nestjs/common';
import { LocalAuthGuard } from './auth/local-auth.guard';
import { JwtAuthGuard } from './auth/jwt-auth.guard';
import { AuthService } from './auth/auth.service';
@Controller()
export class AppController {
constructor(private authService: AuthService) {}
@UseGuards(LocalAuthGuard)
@Post('auth/login')
async login(@Request() req) {
return this.authService.login(req.user);
}
@UseGuards(JwtAuthGuard)
@Get('profile')
getProfile(@Request() req) {
return req.user;
}
}
再次，我们应用我们在 @nestjs/passport 模块配置 passport-jwt 模块时自动为我们提供的 AuthGuard。这个 Guard 由其默认名称 jwt 引用。当我们的 GET /profile 路由被命中时，Guard 将自动调用我们的 passport-jwt 自定义配置逻辑，验证 JWT，并将用户属性分配给 Request 对象。
确保应用正在运行，并使用 cURL 测试路由。
$ # GET /profile
$ curl http://localhost:3000/profile
$ # result -> {"statusCode":401,"message":"Unauthorized"}
$ # POST /auth/login
$ curl -X POST http://localhost:3000/auth/login -d '{"username": "john", "password": "changeme"}' -H "Content-Type: application/json"
$ # result -> {"access_token":"eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJ1c2VybmFtZSI6ImpvaG4iLCJzdWIiOjEsImlhdCI6MTU0MTQ5OTUzNiwiZXhwIjoxNTQxNDk5NTk2fQ.KUhOKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhKKhK